eolymp
bolt
Try our new interface for solving problems
Məsələlər

Hidden triangles

Hidden triangles

Zaman məhdudiyyəti 6 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

На плоскость положили 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

В первой строке вывести количество видимых треугольников. Во второй строке перечислить их номера в произвольном порядке.

Ограничения

1N500

-1000x_ij, y_ij1000, для 1iN, 1j3.

Nümunə

Giriş verilənləri #1
3
1 0 4 0 0 3
-2 1 5 -2 3 4
-2 2 4 1 2 4
Çıxış verilənləri #1
2
2 3