시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB0000.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$-й вершины многоугольника в порядке обхода по часовой стрелке. Никакие три последовательные вершины не должны лежать на одной прямой.

Вещественные числа выводите с точностью не менее шести знаков после запятой.

예제 입력 1

3
0 0
0 1
1 0

예제 출력 1

3
0 0
0 1
1 0

예제 입력 2

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

예제 출력 2

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

힌트

Второй пример соответствует рисунку, приведенному в условии задачи.