Реферат: Iii всероссийская Командная Олимпиада Школьников по Программированию

III Всероссийская Командная Олимпиада Школьников по Программированию

Санкт-Петербург, Дворец Творчества Юных – Барнаул, Гимназия 42, 24 ноября 2002 года

Половинное деление

Имя входного файла:

half.in

Имя выходного файла:

half.out

Максимальное время работы на одном тесте:

2 секунды

^ Максимальный объем доступной памяти:

8 мегабайт

Рассмотрим выпуклый многоугольник, вершины которого лежат в точках плоскости с целыми координатами. Требуется разбить его на треугольники с вершинами в точках с целыми координатами, каждый из которых имел бы площадь ½, либо выяснить, что это сделать невозможно.



Рисунок 1. Разбиение многоугольника на треугольники с площадью ½.

Формат входных данных

Первая строка входного файла содержит число N – количество вершин многоугольника (1 ≤ N ≤ 10). Следующие N строк содержат координаты вершин многоугольника в порядке обхода их по часовой стрелке. Все координаты – целые неотрицательные числа, не превышающие 10. Никакие три последовательные вершины многоугольника не лежат на одной прямой.

Формат выходных данных

Если выполнить разбиение указанным образом невозможно, выведите в выходной файл единственное число – 0.

В противном случае выведите несколько строк, содержащих по 6 чисел каждая. Количество строк должно быть равно количеству треугольников в найденном разбиении. Числа в каждой строке должны представлять собой координаты вершин соответствующего треугольника – x1, y1, x2, y2, x3, y3. Площадь каждого треугольника должна быть ½. Порядок перечисления треугольников и вершин в каждом из треугольников может быть произвольным. Если допустимых разбиений несколько, выведите любое.

Пример

half.in

half.out

4

0 0

0 2

2 2

1 0

0 0 1 1 1 0

0 0 1 1 0 1

0 1 1 1 1 2

0 1 1 2 0 2

1 0 2 2 1 1

1 1 2 2 1 2




Страница из 10