Задача 53: Многоугольники (XV Всеукраинская олимпиада по
информатике)
На плоскости задано такое множество из
N многоугольников, что выполняются следующие условия:
1) никакие два многоугольника не имеют общих точек;
2) для каждого i-го многоугольника существует Pi многоугольников,
внутри которых он находится, и N-1-Pi многоугольников, которые
находятся внутри его, 0 < Pi < N-1.
Задача
Напишите программу POLYGON, которая для каждого многоугольника
выдает количество многоугольников, внутри которых он находится.
Входные данные
Первая строка входного файла POLYGON.DAT содержит целое число N
- количество многоугольников, 3 < N < 10000. Следующие N строк файла
описывают N многоугольников. (i+1)-ая строка файла описывает i-ый
многоугольник. Первое целое число Ci- количество вершин
многоугольника, 3?Ci?20. Последующие Ci пар чисел - координаты
вершин многоугольника в порядке его обхода. Координаты вершин -
целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000
000.
Пример входных данных
3
3 -2 1 8 9 12 1
3 7 5 6 3 7 4
4 4 3 7 7 9 3 1 2
Выходные данные
Единственная строка выходного файла POLYGON.SOL должна содержать
N чисел: i-ое число строки должно быть Pi- количество
многоугольников, внутри которых находится i-ый многоугольник.
Пример выходных данных
0 2 1
Решение:
Когда я первый раз увидел эту задачу, то подумал что она
геометрическая и огорчился (не люблю геометрические задачи, хуже них
только задачи с графами). Но нет, нет геометрии в этой задаче.
Многоугольники не имеют общих точек. Очень важное условие.
Заведем массив, в который для каждого многоугольника запишем его
крайнюю правую координату (можно записать любую другую "самую", но
мы разберем случай с правой координатой). Это самая правая точка
многоугольника. Естественно, что у самого большого многоугольника
самая правая точка будет лежать правее самых правых точек всех
остальных многоугольников. Если бы это было не так, то
многоугольники имели бы точки пересечения, что противоречит условию.
Техническая реализация: Следует завести два массива, в один
из которых записать координаты самых правых точек многоугольника
(только координату по X, ту что отвечает за "правость"), а в другой
- номера многоугольников. Затем отсортируем по убыванию массив
правых координат с помощью быстрой сортировки вместе с
элементами массива координат перемещая элементы массива номеров
многоугольников. После того как массив отсортирован, заполним его
элементы с правой координатой значениями, соответствующими номеру
этого элемента - 1 (т.е. 0, 1, 2...). Теперь в этом массиве хранится
число многоугольников, которые окружают данный многоугольник. Теперь
с помощью другой процедуры быстрой сортировки отсортируем массив
номеров по возрастанию, перемещая соответствующие элементы "правого"
массива. Это делается для ускорения вывода, чтобы не искать каждый
раз элемент в массиве заново.
Теперь просто идя по "правому" массиву от 1 до количества
многоугольников выводим значения - это и есть количество окружающих
многоугольников.
Далее
ð
