printРабочее место участника

printЗадачи

2050. Забор

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Забор вокруг больницы Принстон-Плейнсборо был построен задолго до появления там доктора Хауса, доктора Кадди и всех остальных ее сотрудников, ныне там работающих. Забор представляет собой выпуклый многоугольник. В вершинах этого многоугольника стоят столбы, а его ребрами являются секции забора. Однако, при строительстве забора по ошибке был построен лишний столб, который в итоге оказался внутри забора, то есть на территории больницы, и причинял персоналу и больным много неудобств.
Доктор Кадди решила исправить это досадное упущение, построив вокруг больницы новый забор. Новый забор должен удовлетворять трем условиям:
  • вершинами многоугольника нового забора могут быть только уже существующие столбы (вершины старого и данный столб внутри него)
  • внутри многоугольника, представляющего новый забор, не должно быть столбов, не являющихся вершинами многоугольника
  • его площадь должна быть максимально возможной
При этом многоугольник, представляющий новый забор, может быть невыпуклым, а также некоторые столбы, находящиеся за его территорией, могут остаться неиспользованными.
Первая строка входного файла содержит одно целое число `n` (`3\ ≤\ n\ ≤\ 10^5`) – количество вершин в многоугольнике, представляющем старый забор. Следующие `n` строк содержат по два целых числа `x` и `y`, не превосходящих по абсолютной величине `10^8` – координаты вершин этого многоугольника. Координаты даны в порядке обхода многоугольника против часовой стрелки, многоугольник выпуклый. Никакие три вершины многоугольника не лежат на одной прямой.
Последняя строка входного файла содержит два целых числа `X` и `Y`, не превосходящих по абсолютной величине `10^8` – координаты лишнего столба. Гарантируется, что точка (`X`, `Y`) лежит строго внутри многоугольника.
Опишите многоугольник, представляющий новый забор, в том же формате, в котором описан старый. Внутри нового забора не должно быть столбов и его площадь должна быть максимальна.

Пример ввода

4
-1 -1
1 -1
1 1
-1 1
0 0

Пример вывода

5
-1 -1
0 0
-1 1
1 1
1 -1
Источник: neerc.ifmo.ru/school
loading