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

Условие

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

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

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

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

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

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

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

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

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

• Отрезок: "segment x₁ y₁ x₂ y₂", где (x₁, y₁) и (x₂, y₂) — концы отрезка, отрезок считается направленным от (x₁, y₁) к (x₂, y₂).
• Луч, направленный от начала: "outray x₁ y₁ x₂ y₂", где (x₁, y₁) — начало луча, а (x₂, y₂) — произвольная точка на луче, отличная от начала.
• Луч, направленный к началу: "inray x₁ y₁ x₂ y₂", где (x₂, y₂) — начало луча, а (x₁, y₁) — произвольная точка на луче, отличная от начала.
• Прямая: "line x₁ y₁ x₂ y₂", где (x₁, y₁) и (x₂, y₂) — две точки на прямой, причем при движении вдоль прямой в ее направлении точка (x₁, y₁) следует ранее точки (x₂, y₂).

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

Ограничения

1 ≤ n ≤ 1000

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

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

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
0 0 1 0 0 1
0 0 -1 0 0 1

1
line 1 0 -1 0

2
0 0 1 0 0 1
0 0 -1 0 0 -1

0