#1666

Супермногоугольники

Темы: [Элементарная геометрия] [Минимальный каркас]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2004, Задача G ]

На плоскости задано N (1 ≤ N ≤ 30) супермногоугольников (без пересечений и самопересечений). Каждый супермногоугольник задаётся координатами своих K_i (3 ≤ K_i ≤ 30, 1 ≤ i ≤ N) вершин в порядке обхода против часовой стрелки. Все координаты — целые числа из диапазона -32000..32000. Требуется соединить супермногоугольники М отрезками так, чтобы:

Oтрезок соединяет только пару супермногоугольников.
Суммарная длина отрезков была минимальна.
Между любыми двумя супермногоугольниками должен существовать путь (последовательность некоторых отрезков и частей границ супермногоугольников).

Формат входных данных

В первой строке число N. В следующих N строках. Число K_i и K_i пар чисел – координаты вершин.

Формат выходных данных

В первой строке число М и сумма длин найденных отрезков с точностью 10^-3. В следующих М строках числа L₁ X₁ Y₁ L₂ X₂ Y₂ – номера супермногоугольников и координаты концов отрезков с точностью 10^-3.

Примеры

Входные данные

Выходные данные

2

3 1 0 2 0 1 1

4 6 5 7 5 7 6 6 6

1 6.364

1 1.500 0.500 2 6.000 5.000

3

3 0 0 1 0 0 1

4 5 5 6 5 6 6 5 6

3 0 5 1 6 0 6

2 8.000

3 1.000 6.000 2 5.000 6.000

1 0.000 1.000 3 0.000 5.000

#1684

Радиолокация

Темы: [Элементарная геометрия] [Жадный алгоритм]

Вводится новый авиарейс между городами \(A\) и \(B\). Самолет будет лететь строго по прямой, соединяющей эти города. На протяжении всего пути необходимо, чтобы за самолетом могли наблюдать с земли при помощи радаров. Однако, радиус действия радаров ограничен, и равен \(R\). Хуже того, радарные станции имеются только в определенных точках (например, других населенных пунктах). Руководство авиакомпании желает выяснить: можно ли следить за самолетом на протяжении всего пути из \(A\) в \(B\). Если это возможно, то каким минимальным количеством уже имеющихся радаров можно для этого обойтись. Самолет, находящийся на границе действия радара является видимым, то есть если расстояние от радара до самолета точно равно \(R\), то считается что радар еще действует.

Входные данные

сначала вводятся координаты точек \(A\) и \(B\) (целые числа, по модулю не превышают 1000), затем вводится число \(N\) (натуральное, не превышает 20) – количество уже построенных радаров, затем следует число \(R\) – радиус действия радара (натуральное, не превышает 1000). Затем вводится \(N\) пар чисел – координаты уже построенных радаров (целые, по модулю не превышают 1000). Наличие радаров в городах \(A\) и \(B\) возможно, но необязательно.

Выходные данные

выведите минимальное количество радаров, которое надо задействовать для сопровождения самолета на всем пути. Если сопровождение имеющимися средствами невозможно – выведите число -1.

Примеры

Входные данные

0 0 1 1
1 1
5 5

Выходные данные

-1

Входные данные

Выходные данные

#1697

Четыре камня

Темы: [Элементарная геометрия]

Михаил — маг 80-го уровня. Одно из его изобретений — лабиринт, который дает сверхспособности каждому, кто проходит через него. Лабиринт имеет очень сложную магическую структуру, но внешне выглядит как квадрат, нарисованный на земле.

Михаил нашел подходящее место для лабиринта на берегу Клязьмы. Он нарисовал границу лабиринта палочкой на песке и отметил 4 точки на границах лабиринта так, что на каждой из сторон лабиринта лежал камень и ни один камень не лежал в углу.

В нашем мире все течет и меняется: река Клязьма по весне разлила свои воды, затопив пляж. Изображение на песке стерлось, остались только лежащие камни. Теперь Михаил не может восстановить свой лабиринт.

За помощь в восстановлении лабиринта Михаил обещал научить вас вставлять палочку в одно ухо и вынимать из другого.

Входные данные

В четырех строках входного файла содержатся координаты камней \(x_i\) и \(y_i\) (-1000 ≤ \(x_i\), \(y_i\) ≤ 1000). Точки не совпадают и никакие три точки не лежат на одной прямой.

Выходные данные

Выведите четыре строки, каждая из которых содержит два вещественных числа — координаты вершин квадрата. Вершины должны быть перечислены в порядке обхода по или против часовой стрелки. Числа необходимо выводить с точностью 6 знаков после точки. Если решений несколько — выведите любое из них. Если решений нет — выведите 4 пары нулей

Примеры

Входные данные

Выходные данные

9.0 15.0
15.0 6.0
6.0 0.0
0.0 9.0

Входные данные

Выходные данные

#1712

L-фигуры

Темы: [Элементарная геометрия]

Будем говорить, что два отрезка образуют L-фигуру, если угол между ними составляет 90˚ и конец одного отрезка совпадает с концом другого. На плоскости заданы N отрезков, занумерованных от 1 до N. Требуется определить количество различных L-фигур, образованных этими отрезками. L-фигуры считаются различными, если они содержат отрезки с разными номерами.

Входные данные

Первая строка содержит натуральное число N (1 ≤ N ≤ 5 000) – количество отрезков. Каждая из следующих N строк описывает один отрезок и содержит 4 целых числа x1, y1, x2, y2 (-10 000 ≤ x1, y1, x2, y2 ≤ 10 000), где (x1, y1) и (x2, y2) – концы отрезка. Конечные точки отрезка не совпадают.

Выходные данные

Необходимо вывести одно число — количество различных пар отрезков, образующих L-фигуру.

Пояснение: В примере L-фигуры образованы парами отрезков: (1, 4), (1, 7), (2, 3), (4, 5), (5, 7). Обратите внимание, что отрезки 4 и 7 совпадают, но пары (1, 4) и (1, 7) считаются различными.

#1752

Автобусы

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2003, Задача A ]

Заданы прямоугольные рамки с вершинами в целых точках и со сторонами параллельными осям координат. Требуется найти количество точек, лежащих на всех рамках.

В одном городе недавно запустили автобусную сеть. Однако, плата за проезд для жителей этого города показалась чрезмерной. И несознательные граждане, вместо того, чтобы покупать билет, стали договариваться с водителем и ездить за полцены. Конечно, городская казна понесла серьезные убытки, и было решено взять на работу нескольких контролёров. По уставу, каждый контролёр должен стоять на одном месте и останавливать подозрительные автобусы с целью проверки билетов.

Для повышения эффективности труда контролёров начальство хочет, чтобы через каждую точку, в которой находится контролёр, проходили маршруты всех автобусов. С другой стороны, нельзя ставить нескольких контролёров в одной точке, чтобы они не отвлекались от выполнения своих обязанностей. Наконец, третья сторона, независимый профсоюз, требует от городской администрации принять на работу максимальное количество контролёров.

Для простоты предположим, что действие происходит на координатной плоскости. Каждый автобус ездит по границе прямоугольника c ненулевыми сторонами, вершины которого имеют целочисленные координаты, а стороны параллельны осям координат. Требуется выяснить, какое максимальное число контролёров удастся принять на работу, если городское управление милиции, в свою очередь, требует, чтобы каждый контролёр находился в точке с целочисленными координатами.

Входные данные

На первой строке входного файла находится число \(n\) (1 ≤ \(n\) ≤ \(10^4\)) – количество маршрутов. Далее следуют \(n\) строк, на каждой из которых находятся две пары целых чисел – координаты двух противоположных вершин прямоугольника, по которому проходит данный маршрут. Все координаты не превосходят \(10^8\) по абсолютной величине.

Выходные данные

Выведите в выходной файл одно число – максимальное количество контролёров, которые смогут обрести работу благодаря этому мероприятию.

Примеры

Входные данные

1
0 0 1 1

Выходные данные