시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Фридрих III --- мэр обыкновенного средневекового города. Недавно на этот город стали совершать набеги кочевники. Город окружен надежной крепостной стеной, поэтому коренные жители города надежно защищены. К сожалению, бесчинство кочевников привело к наплыву беженцев, которые стали селиться у крепостной стены за пределами города. Именно они больше всего страдают от набегов. Фридрих считает, что защита беженцев входит в его обязанности, но в данный момент у города нет ресурсов на строительство дополнительной стены.
Оборона города на высоте, поэтому кочевники не рискуют приближаться вплотную к городу. Мэр заметил, что за пределами города существуют точки, которые не видны кочевникам до тех пор, пока те остаются достаточно далеко.
Более формально, представим крепостную стену как многоугольник $P$. Назовем точку $X$ защищенной многоугольником $P$, если любой луч, проведенный из $X$, пересекается с $P$. Например, любая точка внутри $P$ является защищенной. Множество всех защищенных точек также образует многоугольник. Назовем его $Q$.
$P$ | $Q$ |
Мэр решил распространить среди беженцев карту защищенных точек, как мест, рекомендуемых для поселения. Требуется помочь ему составить эту карту.
Задан многоугольник $P$, требуется найти многоугольник $Q$, состоящий из точек, защищенных многоугольником $P$.
Первая строка входного файла содержит целое число $n$ --- число вершин многоугольника $P$, соответствующего крепостной стене ($3 \le n \le 100$). Следующие $n$ строк содержат по два целых числа $x_i$ и $y_i$, разделенных пробелом --- координаты $i$-й вершины многоугольника в порядке обхода по часовой стрелке ($|x_i|, |y_i| \le 10\,000$).
Выведите множество защищенных точек --- многоугольник $Q$.
Сначала выведите число $m$ --- число вершин многоугольника $Q$. Следующие $m$ строк должны содержать по два вещественных числа $x_i$ и $y_i$, разделенных пробелом --- координаты $i$-й вершины многоугольника в порядке обхода по часовой стрелке. Никакие три последовательные вершины не должны лежать на одной прямой.
Вещественные числа выводите с точностью не менее шести знаков после запятой.
3 0 0 0 1 1 0
3 0 0 0 1 1 0
16 0 1 0 3 1 4 4 4 5 3 4 2 3 3 2 3 1 2 2 1 3 2 4 1 5 2 6 1 5 0 1 0
12 0 1 0 3 1 4 4 4 5 3 4 2 3 2 4 1 5 2 6 1 5 0 1 0
Второй пример соответствует рисунку, приведенному в условии задачи.