You are given n segments in the plane, each with two different endpoints. Decide whether some pair of segments shares at least one point. Crossing, touching at an endpoint, and overlapping along a common stretch all count as sharing a point.
The first line has n. Each of the next n lines has four integers x1 y1 x2 y2, the endpoints of one segment.
Print YES if some two segments share a point, otherwise NO.
1 <= n <= 500 |x|, |y| <= 10^9
1000 ms256 MB
2 0 0 4 4 0 4 4 0
YES
The two diagonals of a square cross at (2,2).
2 0 0 1 0 2 0 3 0
NO
Both segments lie on the x-axis, but there is a gap between x = 1 and x = 2.
3 0 0 2 0 1 0 3 0 5 5 6 6
YES
The first two segments overlap on the stretch from x = 1 to x = 2.
