Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит также и отрезок, соединяющий эти точки. Минимальное по включению выпуклое множество, содержащее заданное множество точек \(X\), называется выпуклой оболочкой множества \(X\).
В этой задаче вам требуется найти выпуклую оболочку множества точек, принадлежащих заданному набору углов.
Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.
На рисунке слева приведены два угла, на рисунке справа изображена их выпуклая оболочка.
Формат входных данных
Первая строка содержит число \(n\) — количество углов (\(1 \le n \le 1000\)). Каждая из следующих \(n\) строк описывает углы. Каждый угол описывается координатами трех точек: вершины и двух отличных от вершины точек — по одной на каждом из лучей. Все координаты целые и не превышают \(10^4\) по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.
Формат выходных данных
Выведите границу выпуклой оболочки в виде последовательности направленных лучей, прямых и отрезков. Никакие два объекта в выходном файле не должны лежать на одной прямой. Все отрезки должны иметь длину больше нуля. Объекты должны быть перечислены в таком порядке, чтобы начало каждого следующего совпадало с концом предыдущего. Все числа должны быть целыми и не превосходить \(10^5\) по абсолютной величине. При проходе вдоль описанной границы выпуклая оболочка углов должна быть справа.
На первой строке выведите \(l\) — количество объектов в ответе. Следующие \(l\) строк должны содержать описание объектов. Объекты описываются следующим образом:
-
Отрезок: <<segment \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_1, y_1)\) и \((x_2, y_2)\) — концы отрезка, отрезок считается направленным от \((x_1, y_1)\) к \((x_2, y_2)\).
-
Луч, направленный от начала: <<outray \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_1, y_1)\) — начало луча, а \((x_2, y_2)\) — произвольная точка на луче, отличная от начала.
-
Луч, направленный к началу: <<inray \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_2, y_2)\) — начало луча, а \((x_1, y_1)\) — произвольная точка на луче, отличная от начала.
-
Прямая: <<line \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_1, y_1)\) и \((x_2, y_2)\) — две точки на прямой, причем при движении вдоль прямой в ее направлении точка \((x_1, y_1)\) следует ранее точки \((x_2, y_2)\).
Если выпуклой оболочкой является вся плоскость, то выведите \(l = 0\).
Примеры
| № | Входные данные | Выходные данные |
|
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 0 0 -1 0
|
|
3
|
2
0 0 1 0 0 1
0 0 -1 0 0 -1
|
0
|