eolymp
bolt
Try our new interface for solving problems
Problems

Hidden triangles

Hidden triangles

\textbf{N} triangles are put on the plane in order from \textbf{1} to \textbf{N}. Whole inside region of each triangle is opaque and closes everything behind it. Determine, which of the triangles are visible on the plane. I.e. have positive area, not covered above with any other triangle. \InputFile In the rst line number \textbf{N} is amount of triangles. Then in \textbf{N} lines triangles are listed in the order they were put to the plane. Each triangle is de ned with \textbf{6} integers \textbf{x_i1},\textbf{y_i1}, \textbf{x_i2}, \textbf{y_i2}, \textbf{x_i3}, \textbf{y_i3}, which are coordinates of each verticle. All the triangles are not degenerated. Any edge of a triangle has no more than one common point with any edge of anoter triangle. \OutputFile Output amount of visilbe triangles in the rst line. List their numbers in any order in the second line. \textbf{Limits} \textbf{1} ≤ \textbf{N} ≤ \textbf{500} \textbf{-1000} ≤ \textbf{x_ij}, \textbf{y_ij} ≤ \textbf{1000}, for \textbf{1} ≤ \textbf{i} ≤ \textbf{N}, \textbf{1} ≤ \textbf{j} ≤ \textbf{3}.
Time limit 6 seconds
Memory limit 256 MiB
Input example #1
3
1 0 4 0 0 3
-2 1 5 -2 3 4
-2 2 4 1 2 4
Output example #1
2
2 3