Problems
Segments intersection - 2
Segments intersection - 2
\textbf{n} segments are given on the \textbf{2-D} plane. Are they intersect? (the set of segments intersect if there exist two of them that have at least one common point)
\InputFile
Each line contains the integer coordinates of segment endpoints (\textbf{x_1}, \textbf{y_1}) - (\textbf{x_2}, \textbf{y_2}). It is known that \textbf{n }≤ \textbf{6*10^5} and \textbf{-2000} ≤ \textbf{x_1}, \textbf{y_1}, \textbf{x_2}, \textbf{y_2} ≤ \textbf{2000}.
\OutputFile
Print "\textbf{intersect}" if segments intersect or "\textbf{NOT intersect}" otherwise.
Input example #1
1 1 6 3 6 1 9 3 2 5 7 3 2 3 4 3 7 2 10 1
Output example #1
intersect