eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Hidden triangles

Hidden triangles

На плоскость положили \textbf{N} треугольников по порядку от \textbf{1} до \textbf{N}. Вся внутренняя область каждого треугольника является непрозрачной и закрывает все, что находится под ней. Определить, какие из треугольников остались видны на плоскости. То есть имеют область положительной площади, не накрытую сверху никаким другим треугольником. \InputFile В первой строке число \textbf{N} --- количество треугольников. Далее в \textbf{N} строках перечислены треугольники в том порядке, в котором они выкладывались на плоскость. Каждый треугольник описывается шестью целыми числами \textbf{x_i1},\textbf{y_i1}, \textbf{x_i2}, \textbf{y_i2}, \textbf{x_i3}, \textbf{y_i3} --- координатами его вершин. Все треугольники невырожденные. Любая сторона одного треугольника имеет не более одной общей точки с любой стороной другого треугольника. \OutputFile В первой строке вывести количество видимых треугольников. Во второй строке перечислить их номера в произвольном порядке. \textbf{Ограничения} \textbf{1} ≤ \textbf{N} ≤ \textbf{500} \textbf{-1000} ≤ \textbf{x_ij}, \textbf{y_ij} ≤ \textbf{1000}, для \textbf{1} ≤ \textbf{i} ≤ \textbf{N}, \textbf{1} ≤ \textbf{j} ≤ \textbf{3}.
Лимит времени 6 секунд
Лимит использования памяти 256 MiB
Входные данные #1
3
1 0 4 0 0 3
-2 1 5 -2 3 4
-2 2 4 1 2 4
Выходные данные #1
2
2 3