POLYGON

  • Многоугольник
    POLYGON


Описание
Точками многоугольника являются как его внутренние точки, так и точки на границе. Выпуклым многоугольником называется такой многоугольник, в котором для любых двух его точек X и Y отрезок, соединяющий X и Y, полностью принадлежит многоугольнику. Все многольники в этой задаче выпуклые и содержат не менее 2-х вершин. Все вершины любого многоугольника в этой задаче различны и имеют целочисленные координаты. Никакие три вершины не лежат на одной прямой. Слово "многоугольник" далее всегда обозначает именно такие многоугольники. 

Для двух данных многоугольников A и B их суммой Минковского называется фигура, состоящая из всех точек вида (x1+x2,y1+y2), где (x1,y1) - все возможные точки многоугольника A, и (x2,y2) - все возможные точки многоугольника B. Оказывается, что сумма Минковского двух многоугольников также является многоугольником. Рисунок иллюстрирует сумму Минковского для двух треугольников


Будем рассматривать операцию, обратную сумме Минковского. Для данного многоугольника P требуется найти такие два многоугольника A и B, что:

  • P является суммой Минковского A и B

  • A имеет от 2 до 4 различных вершин, то есть это отрезок (2 вершины), треугольник (3 вершины) или четырехугольник (4 вершины)

  • A должен иметь как можно больше вершин, то есть

    • A должен быть четырехугольником, если это возможно

    • если A не может быть четырехугольником, он должен быть треугольником, если это возможно

    • иначе он должен быть отрезком

Очевидно, что ни A и ни B не может быть равен P, поскольку в этом случае один из многоугольников A или B должен быть точкой, что не является многоугольником по определению.

Задача
Вам дан набор входных файлов, каждый из которых содержит описание многоугольника P. Для каждого входного файла вы должны найти многоугольники A и B такие, как описано выше, и создать выходной файл, содержащий описания A и B. Гарантируется, что для каждого из данных входных файлов такие многоугольники существуют. Если существует несколько вариантов ответа, запишите любой из них. Вы не должны сдавать какие-либо программы, вы должны сдать на проверку только выходные файлы. 


Формат входных данных
Вам дан набор из 10 входных файлов с названиями POLYGON1.IN, POLYGON2.IN, ..., POLYGON10.IN, где число после слова POLYGON является номером теста. 

Каждый входной файл имеет следующий формат: первая строка содержит одно целое число N - количество вершин многоугольника P. Следующие N строк описывают вершины многоугольника в порядке их обхода против часовой стрелки, по одной вершине в строке. Строка I+1 (I=1,2,...,N) содержит два целых числа XI и YI, разделенных пробелом: координаты I-ой вершины многоугольника. Все координаты во входных файлах - неотрицательные целые числа

Формат выходных данных
Вы должны сдать 10 выходных файлов, соответствующих данным входным файлам с описаниями искомых многоугольников A и B. Первая строка каждого выходного файла должна содержать текст:

#FILE POLYGON I, где целое число I (1<=I<=10) является номером соответствующего входного файла

Далее формат выходного файла подобен формату входного файла. Вторая строка должна содержать одно целое число NA - количество вершин многоугольника A (2<=NA<=4). Следующие NA строк должны описывать вершины многоугольника A в порядке обхода против часовой стрелки, по одной вершине в строке. Строки с номерами I+2 (I=1,2,...,NA) должны содержать по два целых числа X и Y - координаты I-ой вершины многоугольника A. Числа в строке должны разделяться одним пробелом. 

Строка NA+3 должна содержать одно целое число NB - количество вершин многоугольника B, (2<=NB). Следующие NB строк должны описывать вершины многоугольника B в порядке обхода против часовой стрелки, по одной вершине в строке. Строки с номерами NA+J+3 (J=1,2,...,NB) должны содержать по два целых числа X и Y - координаты J-ой вершины многоугольника B. Числа в строке должны разделяться одним пробелом. 


Например:

POLYGON0.IN
5
0  1
0  0
2  0
2  1
1  2


Для приведенного входного файла любой из двух приведенных ниже выходных файлов корректен, так как в обоих случаях A является треугольником и не может быть четырехугольником

#FILE POLYGON 0
3
0  0
2  0
2
0  1
0  0


или

 

#FILE POLYGON 0
3
0  0
1  0
1  1
3
0  1
0  0
1  0