Мише исполнилось \(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
Многоугольник топят в жидкости, опуская его из воздуха с постоянной скоростью v метров в минуту. Жидкость разъедает многоугольник со всех сторон с постоянной скоростью c метров в минуту. Для точки (\(x\), \(y\)) внутри многоугольника, опускающейся вместе с ним, выясните, в какой момент разъедающая жидкость доберётся до этой точки.
Граница между воздухом и жидкостью проходит по прямой \(y\)=0. Жидкость разъедает многоугольник как двумерную фигуру. Многоугольник не поворачивается при опускании в жидкость, и в момент времени 0 он не касается жидкости.
В отличие от многоугольника, который считается двумерным, жидкость существует в трёх измерениях. Поэтому она проникает внутрь «дыр» в многоугольнике. Например, если многоугольник имеет форму «чашки», жидкость проникает «внутрь», как показано на рисунке.
В первой строке входного файла записано через пробел пять целых чисел \(n\), \(x\), \(y\), \(v\) и \(c\) (3 \(\le\) \(n\) \(\le\) 30, −100 \(\le\) \(x\) \(\le\) 100, 1 \(\le\) \(y\) \(\le\) 100, 1 \(\le\) \(c\) < \(v\) \(\le\) 100). Следующие \(n\) строк описывают вершины многоугольника; \(i\)-я из них содержит два целых числа \(x\) и \(y\) через пробел (−100 \(\le\) \(x\) \(\le\) 100, 1 \(\le\) \(y\) \(\le\) 100). Вершины даны в порядке обхода против часовой стрелки. Многоугольник не имеет самопересечений и самокасаний, а точка (\(x\), \(y\)) лежит строго внутри него.
Выведите одно число — время, которое потребуется жидкости, чтобы добраться до точки (\(x\), \(y\)), с точностью не менее четырёх знаков после запятой.
4 0 50 2 1 -1 10 1 10 1 90 -1 90
25.8660
На плоскости даны \(N\) точек. Вам требуется построить выпуклую оболочку данного множества точек. Если \(N\) нечетно, то оболочку нужно выводить в порядке обхода по часовой стрелке, иначе — против часовой стрелки.
Первая строка содержит количество точек \(N\), \(1\le N\le 20\,000\). Каждая из последующих \(N\) строк содержит два целых числа — координаты \(x_i\) и \(y_i\). Все числа по модулю не превосходят \(10^4\).
Выходной файл должен иметь тот же формат, что и входной, и должен содержать выпуклую оболочку. Количество точек в выходном файле должно быть минимально возможным.
4 0 0 3 4 3 1 6 0
3 6 0 3 4 0 0
К 2110 году город Флэтбург, являясь одним из крупнейших городов мира, не имеет обходной автомагистрали, что является существенным препятствием для его развития как крупнейшего транспортного центра мирового значения. В связи с этим ещё в 2065 году при разработке Генерального плана развития Флэтбурга была определена необходимость строительства кольцевой автомобильной дороги.
В Генеральном плане также были обозначены требования к этой дороге. Она должна соответствовать статусу кольцевой — иметь форму окружности. Кроме этого, четыре крупные достопримечательности Флэтбурга должны быть в одинаковой транспортной доступности от дороги. Это предполагается обеспечить тем, что они будут находиться на равном расстоянии от неё. Расстоянием от точки расположения достопримечательности до дороги называется наименьшее из расстояний от этой точки до некоторой точки, принадлежащей окружности автодороги.
Требуется написать программу, которая вычислит число возможных планов постройки кольцевой автомобильной дороги с соблюдением указанных требований и найдёт такой план, для которого длина дороги будет минимальной. Гарантируется, что хотя бы один план постройки существует.
Входной файл содержит четыре строки. Каждая из них содержит по два целых числа: \(x_i\) и \(y_i\) — координаты места расположения достопримечательности. Первая строка описывает первую достопримечательность, вторая — вторую, третья — третью, четвёртая — четвёртую. Никакие две достопримечательности не находятся в одной точке.
Все числа во входном файле не превосходят 100 по абсолютной величине.
В первой строке выходного файла требуется вывести число возможных планов постройки кольцевой автомобильной дороги. Если таких планов бесконечно много, необходимо вывести в первой строке выходного файла слово Infinity.
На второй строке требуется вывести координаты центра дороги минимальной длины и её радиус. Если существует несколько разных способов построения дороги минимальной длины, необходимо вывести координаты центра и радиус любой из них. Координаты центра и радиус должны быть выведены с точностью не хуже \(10^{-5}\) и не должны превышать \(10^9\). Гарантируется, что существует хотя бы один план с такими параметрами.
0 0 0 1 1 0 2 2
7 1.5 0.5 1.14412281
0 0 0 1 1 0 1 1
Infinity 0.5 0.5 0.0