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