29296번 - Забор 스페셜 저지다국어

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

Доктор Кадди решила исправить это досадное упущение, построив вокруг больницы новый забор. Новый забор должен удовлетворять трем условиям:

• вершинами многоугольника нового забора могут быть только уже существующие столбы (вершины старого и данный столб внутри него)
• внутри многоугольника, представляющего новый забор, не должно быть столбов, не являющихся вершинами многоугольника
• его площадь должна быть максимально возможной

При этом многоугольник, представляющий новый забор, может быть невыпуклым, а также некоторые столбы, находящиеся за его территорией, могут остаться неиспользованными.

Первая строка входного файла содержит одно целое число $n$ ($3 \le n \le 10^5$) --- количество вершин в многоугольнике, представляющем старый забор. Следующие $n$ строк содержат по два целых числа $x$ и $y$, не превосходящих по абсолютной величине $10^8$ --- координаты вершин этого многоугольника. Координаты даны в порядке обхода многоугольника против часовой стрелки, многоугольник выпуклый. Никакие три вершины многоугольника не лежат на одной прямой.

Последняя строка входного файла содержит два целых числа $X$ и $Y$, не превосходящих по абсолютной величине $10^8$ --- координаты лишнего столба. Гарантируется, что точка ($X$, $Y$) лежит строго внутри многоугольника.

Опишите многоугольник, представляющий новый забор, в том же формате, в котором описан старый. Внутри нового забора не должно быть столбов и его площадь должна быть максимальна.