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 40 00 22 21 0 0 0 1 1 1 00 0 1 1 0 10 1 1 1 1 20 1 1 2 0 21 0 2 2 1 11 1 2 2 1 2 Страница из 10