Задача E. Выпуклая оболочка

Автор:Восьмая всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:convex.in   Ограничение памяти:256 Мб
Выходной файл:convex.out  

Условие

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

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

Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.

На рисунке слева приведены два угла, на рисунке справа изображена их выпуклая оболочка.

Формат входного файла

Первая строка входного файла содержит число n — количество углов. Каждая из следующих n строк описывает углы. Каждый угол описывается координатами трех точек: вершины и двух отличных от вершины точек — по одной на каждом из лучей.

Формат выходного файла

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

На первой строке выведите l — количество объектов в ответе. Следующие l строк должны со- держать описание объектов. Объекты описываются следующим образом:

Если выпуклой оболочкой является вся плоскость, то выведите l = 0.

Ограничения

1 ≤ n ≤ 1000

Все координаты целые и не превышают 104 по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.

Примеры тестов

Входной файл (convex.in) Выходной файл (convex.out)
1
2
3 1 4 1 4 4
2 2 4 3 3 4
3
inray 4 1 3 1
segment 3 1 2 2
outray 2 2 3 5
2
2
0 0 1 0 0 1
0 0 -1 0 0 1
1
line 1 0 -1 0
3
2
0 0 1 0 0 1
0 0 -1 0 0 -1
0

0.052s 0.012s 17