Time Limit: 1 sec
Memory Limit: 16MB
You're given n segments in the rectangular coordinate system. The segments are defined by start and end points (Xi,Yi) and (Xj,Yj) (1 <= i, j <= n). Coordinates of these points are integer numbers with real value smaller then 1000. Length of each segment is positive.
When 2 segments don't have a common point then it is said that segments don't collide. In any other case segments collide. Be aware that segments collide even if they have only one point in common.
Segment is said to be isolated if it doesn't collide with all the other segments that are given, i.e. segment i is isolated when for each 1 <= j <= n, (i != j), segments i and j don`t collide. You are asked to find number T - how many segments are isolated.
6
3
0 0 2 0
1 -1 1 1
2 2 3 3
2
0 0 1 1
1 0 0 1
2
0 0 0 1
0 2 0 3
2
0 0 1 0
1 0 2 0
2
0 0 2 2
1 0 1 1
2
1 3 1 5
1 0 1 6
1
0
2
0
0
0
Problem setters: Aleksej Viktorchik, Leonid Shishlo.
Huge Easy Contest #1