В одном городе недавно запустили автобусную сеть. Однако, плата за проезд для жителей этого города показалась чрезмерной. И несознательные граждане, вместо того, чтобы покупать билет, стали договариваться с водителем и ездить за полцены. Конечно, городская казна понесла серьезные убытки, и было решено взять на работу нескольких контролёров. По уставу, каждый контролёр должен стоять на одном месте и останавливать подозрительные автобусы с целью проверки билетов.
Для повышения эффективности труда контролёров начальство хочет, чтобы через каждую точку, в которой находится контролёр, проходили маршруты всех автобусов. С другой стороны, нельзя ставить нескольких контролёров в одной точке, чтобы они не отвлекались от выполнения своих обязанностей. Наконец, третья сторона, независимый профсоюз, требует от городской администрации принять на работу максимальное количество контролёров.
Для простоты предположим, что действие происходит на координатной плоскости. Каждый автобус ездит по границе прямоугольника c ненулевыми сторонами, вершины которого имеют целочисленные координаты, а стороны параллельны осям координат. Требуется выяснить, какое максимальное число контролёров удастся принять на работу, если городское управление милиции, в свою очередь, требует, чтобы каждый контролёр находился в точке с целочисленными координатами.
На первой строке входного файла находится число \(n\) (1 ≤ \(n\) ≤ \(10^4\)) – количество маршрутов. Далее следуют \(n\) строк, на каждой из которых находятся две пары целых чисел – координаты двух противоположных вершин прямоугольника, по которому проходит данный маршрут. Все координаты не превосходят \(10^8\) по абсолютной величине.
Выведите в выходной файл одно число – максимальное количество контролёров, которые смогут обрести работу благодаря этому мероприятию.
1 0 0 1 1
4
В одной далекой стране ученые обнаружили странное скопление камней. Изучив его, ученые пришли к выводу, что это части старой крепостной стены, имевшей форму окружности. К сожалению, время и вандалы разрушили некоторые части стены.
Чтобы защитить оставшиеся фрагменты стены и продолжить их изучение в спокойной обстановке, ученые хотят обнести фрагменты стены забором из колючей проволоки. Если сделать отдельный забор для каждого фрагмента, будет неудобно переходить от одного фрагмента к другому, поэтому ученые хотят сделать один общий забор, окружающий все фрагменты.
Помогите ученым посчитать минимальную возможную длину забора, чтобы они знали, сколько просить колючей проволоки.
Во входном файле задано два натуральных числа: число фрагментов \(n\) (1 ≤ \(n\) ≤ 180) и радиус крепости \(r\) (1 ≤ \(r\) ≤ 100). Далее следует n пар целых чисел, описывающих сохранившиеся фрагменты стены: \(a_i\), \(b_i\) – углы в градусах, соответствующие началу и концу фрагмента. Углы отмеряются от направления на север из центра крепости, против часовой стрелки (0 ≤ \(a_i\), \(b_i\)< 360, \(a_i\) ≠ \(b_i\)). Каждый фрагмент от начального угла к конечному также проходится против часовой стрелки. Фрагменты не имеют общих точек.
Выведите минимальную возможную длину забора. Ответ должен отличаться от правильного не более, чем на \(10^{-3}\).
1 100 0 90
298.5009889168
Мише исполнилось \(n\) лет. Праздничный торт, испеченный по этому случаю, имеет форму круга радиуса \(r\) с центром в начале координат. На торте стоят \(n\) свечек. Мишина мама разделила торт на части, сделав \(m\) прямолинейных разрезов. Каждый гость взял один из получившихся кусков.
Миша хочет узнать, не досталось ли кому-нибудь из его гостей более одной свечки. Помогите ему это выяснить.
Первая строка входного файла содержит целые числа \(n\), \(m\) и \(r\) (1 ≤ \(n\) ≤ 10000, 0 ≤ \(m\) ≤ 1000, 1 ≤ \(r\) ≤ 2000).
Следующие n строк содержат пары целых чисел \(x_i\), \(y_i\) – координаты точек, где расположены свечки. Гарантируется, что эти точки лежат внутри круга, размерами свечек следует пренебречь. Никакие две свечки не совпадают.
Последние \(m\) строк содержат описание разрезов – тройки целых чисел \(a_i\), \(b_i\), \(c_i\). Такая тройка соответствует разрезу, который задается уравнением \(a_i\) \(x\) + \(b_i\) \(y\) + \(c_i\) = 0. Ни один разрез не проходит через свечку. Никакие два разреза не совпадают. Числа ai, bi, ci не превышают 10000 по модулю.
Если одному из гостей досталось более одной свечки, выведите в выходной файл слово «YES», иначе выведите слово «NO».
3 2 3 2 2 1 -1 -2 0 2 -1 0 0 1 -1
NO
3 2 3 2 2 1 -1 -2 0 1 1 -1 0 1 -1
YES
4 2 10 1 1 1 -1 -1 1 -1 -1 0 1 0 1 0 0
NO
Паук и паучиха плывут по озеру на двух веточках. Плавать они не умеют, поэтому смогут встретиться только тогда, когда веточки соприкоснутся.
Считая, что веточки имеют форму отрезков, и что они плывут с постоянными скоростями, определите, сколько осталось ждать встречи несчастным членистоногим.
Входной файл содержит 12 чисел: \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(x_3\), \(y_3\), \(x_4\), \(y_4\), \(v_{1x}\), \(v_{1y}\), \(v_{2x}\), \(v_{2y}\). Координаты вершин первого отрезка: (\(x_1\), \(y_1\)) и (\(x_2\), \(y_2\)), координаты вершин второго отрезка: (\(x_3\), \(y_3\)) и (\(x_4\), \(y_4\)), скорость первого отрезка (\(v_{1x}\), \(v_{1y}\)), скорость второго отрезка (\(v_{2x}\), \(v_{2y}\)). Все числа целые и не превосходят по модулю \(10^4\). В начальный момент времени веточки не соприкасаются. Гарантируется, что веточки имеют ненулевую длину.
Выведите в выходной файл время до ближайшего момента, когда веточки соприкоснутся, с ошибкой не более \(10^{-4}\). Если веточки не соприкоснутся никогда, выведите число -1.
0 0 -1 3 4 4 7 7 3 0 0 -1
1.6
0 0 -1 3 4 4 7 7 1 0 0 -3
-1
Кальпас — обычный говорящий пес, который живет в зоопарке на Марсе. К сожалению, условия содержания животных там не самые лучшие. Кальпаса выпускают на прогулку только раз в день, да и то, «выпускают» — не самое лучшее слово. Двое охранников: Вася и К-20071027, надевают на Кальпаса специальный ошейник и выводят его во двор. Ошейник полностью контролирует перемещения пса: в любой момент Кальпас находится в точности на середине отрезка между своими охранниками.
К сожалению, тот, кто изобрел этот ошейник, совершенно не думал о собаках. Как любому псу, Кальпасу хочется за время своей прогулки пробежать по строго определенному пути. Как же ему это сделать? Кальпас решил договориться со своими охранниками. Поскольку Вася — робот, который движется каждый день по заданному в его программе маршруту с постоянной скоростью, договориться с ним нет никакой возможности. Единственное, что остается Кальпасу — договориться с К-20071027.
Для того, чтобы подготовиться к переговорам, Кальпас хочет выяснить, путь какой длины должен пройти К-20071027, чтобы Кальпас двигался по намеченному пути с постоянной скоростью.
Входной файл содержит описание двух маршрутов, являющихся ломаными линиями: пути, по которому хочет пройти Кальпас и маршрута, по которому ежедневно ходит Вася.
Первая строка описания каждого из маршрутов содержит количество вершин ломаной, а последующие задают координаты этих вершин. Количество вершин в каждой ломаной не превышает 100, координаты точек целые и по модулю не превышают 1000.
В выходной файл выведите длину пути, который должен будет пройти К-20071027 с точностью не менее 10 - 6.
4 0 0 0 6 6 6 6 0 3 0 0 3 3 6 0
30.59411708155670700000