Задача B. Защита беженцев ≡
| Автор: | Жюри ВКОШП-2011 | Автор задачи: Алексей Цыпленков, Автор условия: Антон Банных | Ограничение времени: | 2 сек | |
| Входной файл: | guard.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | guard.out |
Условие
Фридрих III — мэр обыкновенного средневекового города. Недавно на этот город стали совершать набеги кочевники. Город окружен надежной крепостной стеной, поэтому коренные жители города надежно защищены. К сожалению, бесчинство кочевников привело к наплыву беженцев, которые стали селиться у крепостной стены за пределами города. Именно они больше всего страдают от набегов. Фридрих считает, что защита беженцев входит в его обязанности, но в данный момент у города нет ресурсов на строительство дополнительной стены.
Оборона города на высоте, поэтому кочевники не рискуют приближаться вплотную к городу. Мэр заметил, что за пределами города существуют точки, которые не видны кочевникам до тех пор, пока те остаются достаточно далеко.
Более формально, представим крепостную стену как многоугольник P. Назовем точку X защищенной многоугольником P, если любой луч, проведенный из X, пересекается с P. Например, любая точка внутри P является защищенной. Множество всех защищенных точек также образует многоугольник. Назовем его Q.
На рисунке серым цветом показаны точки из Q, но не из P.
Мэр решил распространить среди беженцев карту защищенных точек, как мест, рекомендуемых для поселения. Требуется помочь ему составить эту карту.
Задан многоугольник P, требуется найти многоугольник Q, состоящий из точек, защищенных многоугольником P.
Формат входного файла
Первая строка входного файла содержит целое число n — число вершин многоугольника P, соответствующего крепостной стене (3 ≤ n ≤ 100). Следующие n строк содержат по два целых числа xi и yi, разделенных пробелом — координаты i-й вершины многоугольника в порядке обхода по часовой стрелке (|xi|, |yi| ≤ 104).
Формат выходного файла
Выведите множество защищенных точек — многоугольник Q.
Сначала выведите число m — число вершин многоугольника Q. Следующие m строк должны содержать по два вещественных числа xi и yi, разделенных пробелом — координаты i-й вершины многоугольника в порядке обхода по часовой стрелке. Никакие три последовательные вершины не должны лежать на одной прямой.
Вещественные числа выводите с точностью не менее шести знаков после запятой.
Примеры тестов
| № | Входной файл (guard.in) |
Выходной файл (guard.out) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|