Hidden triangles
Hidden triangles
На плоскость положили N треугольников по порядку от 1 до N. Вся внутренняя область каждого треугольника является непрозрачной и закрывает все, что находится под ней.
Определить, какие из треугольников остались видны на плоскости. То есть имеют область положительной площади, не накрытую сверху никаким другим треугольником.
Giriş verilənləri
В первой строке число N — количество треугольников. Далее в N строках перечислены треугольники в том порядке, в котором они выкладывались на плоскость. Каждый треугольник описывается шестью целыми числами x_i1,y_i1, x_i2, y_i2, x_i3, y_i3 — координатами его вершин. Все треугольники невырожденные. Любая сторона одного треугольника имеет не более одной общей точки с любой стороной другого треугольника.
Çıxış verilənləri
В первой строке вывести количество видимых треугольников. Во второй строке перечислить их номера в произвольном порядке.
Ограничения
1 ≤ N ≤ 500
-1000 ≤ x_ij, y_ij ≤ 1000, для 1 ≤ i ≤ N, 1 ≤ j ≤ 3.
Nümunə
3 1 0 4 0 0 3 -2 1 5 -2 3 4 -2 2 4 1 2 4
2 2 3