Министерство дорожного транспорта решило построить себе новый офис. Поскольку министр регулярно выезжает с инспекцией наиболее важных трасс, было решено, что офис министерства не должен располагаться слишком далеко от них.
Наиболее важные трассы представляют собой прямые на плоскости. Министерство хочет выбрать такое расположение для своего офиса, чтобы максимум из расстояний от офиса до трасс был как можно меньше.
Требуется написать программу, которая по заданному расположению наиболее важных трасс определяет оптимальное расположение дома для офиса министерства дорожного транспорта.
Первая строка входного файла содержит одно целое число \(n\) — количество наиболее важных трасс (\(1 \le n \le 10^4\)).
Последующие \(n\) строк описывают трассы. Каждая трасса описывается четырьмя целыми числами \(x_1\), \(y_1\), \(x_2\) и \(y_2\) и представляет собой прямую, проходящую через точки \((x_1, y_1)\) и \((x_2, y_2)\). Координаты заданных точек не превышают по модулю \(10^4\). Точки \((x_1, y_1)\) и \((x_2, y_2)\) ни для какой прямой не совпадают.
Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать \(10^9\), гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.
Ответ должен иметь абсолютную или относительную погрешность не более \(10^{-6}\), что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет засчитан, если значение выражения \(|x - y| / max(1, |y|)\) не превышает \(10^{-6}\).
Правильные решения для тестов, в которых \(n \le 100\) и все прямые параллельны, оцениваются из 20 баллов.
Правильные решения для тестов, в которых \(n \le 100\) и все прямые параллельны осям координат, оцениваются из 20 баллов.
Правильные решения для тестов, в которых \(n \le 100\), оцениваются из 70 баллов (в эти баллы включаются также по 20 баллов за случаи, описанные в предыдущих двух абзацах).
4 0 0 0 1 0 0 1 0 1 1 2 1 1 1 1 2
0.5000000004656613 0.4999999995343387
7 376 -9811 376 -4207 6930 -3493 6930 -8337 1963 -251 1963 -5008 -1055 9990 -684 9990 3775 -348 3775 1336 7706 -2550 7706 -8412 -9589 8339 -4875 8339
4040.9996151750674 12003.999615175067
На уроке геометрии семиклассники Вася и Петя узнали, что такое параллелограмм. На перемене после урока они стали играть в игру: Петя называл координаты четырех точек в произвольном порядке, а Вася должен был ответить, являются ли эти точки вершинами параллелограмма.
Вася, если честно, не очень понял тему про параллелограммы, и ему требуется программа, умеющая правильно отвечать на Петины вопросы.
Напомним, что параллелограммом называется четырехугольник, противоположные стороны которого равны и параллельны.
В первой строке входного файла записано целое число \(N\) (\(1 \leq N \leq 10\)) - количество заданных Петей вопросов. Каждая из \(N\) последующих строк содержит описание четырех точек - четыре пары целых чисел \(X\) и \(Y\) (\(-100 \leq X\leq 100\), \(-100\leq Y \leq 100\)), обозначающих координаты точки. Гарантируется, что четыре точки, о которых идет речь в одном вопросе, не лежат на одной прямой.
Для каждого из вопросов выведите "YES", если четыре заданные точки могут образовать параллелограмм, и "NO" в противном случае. Ответ на каждый из запросов должен быть в отдельной строке без кавычек.
3 1 1 4 2 3 0 2 3 1 1 5 2 2 3 3 0 0 0 5 1 6 3 1 2
YES NO YES
На одну Очень Известную Планету упал метеорит. Метеорит в атмосфере распался на \(N\) кусков, каждый из которых упал в свою точку.
Чтобы куски метеорита не были испорчены любопытными туристами, для проведения научных исследований решили построить один забор, которым огородить не менее \(K\) кусков метеорита. Естественно, что забор должен быть минимально возможной длины, и внутри него должны оказаться любые \(K\) (или больше) кусков метеорита (кусок считается лежащим внутри забора как когда он лежит строго внутри, так и когда забор проходит непосредственно через него).
Конечно, ученые хотят огородить как можно больше кусков, но как всегда, все упирается в деньги. Главный бухгалтер решил составить такую таблицу: для каждого \(K\) от 1 до \(N\) определить, какой минимальной длины нужно построить забор, чтобы внутри него оказалось не менее \(K\) кусков метеорита. Помогите ему.
В первой строке входного файла записано единственное целое число \(N\). В каждой из следующих \(N\) строк записано по паре целых чисел, по модулю не превосходящих \(1\,000\) - координаты точек, куда упали куски метеорита. Никакие два куска не упали в одну и ту же точку.
Выведите \(N\) чисел, \(i\)-е (\(1 \le i \le N\)) должно быть равно минимальной длине забора, внутри которого окажется не менее \(K\) кусков метеорита. Выведенный ответ будет сравниваться с правильным с точностью до \(10^{-6}\).
Тесты состоят из четырёх групп.
4 0 0 0 1 1 0 1 1
0.000000000 2.000000000 3.414213562 4.000000000
3 1 1 0 0 2 0
0.000000000 2.828427125 4.828427125
Подсчитайте площадь заданного многоугольника.
В первой строке входного файла находится число \(N\) (\(3 \leq N \leq 50000\)) – количество вершин многоугольника. Последующие \(N\) строк содержат по 2 целых числа \(x\) и \(y\) (\(-10000 \leq x,y \leq 10000\)) – координаты вершин.
Выведите в выходной файл площадь многоугольника с точностью 600 знаков после запятой. Незначащие нули при этом тоже нужно выводить.
3 0 0 1 0 0 1
0.500000000000000...000
Выходной файл содержит 600 нулей.
На плоскости даны две окружности. Ваша задача – найти все их общие точки.
В первой строке входного файла находится число \(K\) (\(1 \leq K \leq 10000\)) – количество пар окружностей. Каждая последующая пара строк описывает пару окружностей: в каждой строке записаны 3 целых числа \(x\), \(y\), \(r\) – координаты центра и радиус соответствующей окружности (\(-1000 \leq x,y \leq 1000\), \(0 < r \leq 1000\)).
Для каждой пары окружностей вы должны вывети одну из следующих фраз: “There are no points!!!” – если окружности не пересекаются. “There are only i of them....” – если окружности пересекаются ровно в \(i\) точках. В этом случае последующие \(i\) строк должны содержать координаты точек пересечения в формате \(x\) \(y\). Точки должны быть выведены в лексикографическом порядке (сначала с меньшей координатой \(x\), а при равных \(x\) – сначала с меньшей \(y\)). Координаты следует выводить с 6 знаками после запятой. “I can't count them - too many points :(” – если точек пересечения бесконечно много. Все фразы должны быть выведены без кавычек. Вывод для каждой следующей пары окружностей должен быть отделен от предыдущего одной пустой строкой.
2 0 0 2 4 0 2 0 0 1 1000 1000 1
There are only 1 of them.... 2.000000 0.000000 There are no points!!!