HUST Monthly 2010.06.13
From: 20100613 12:00:00
To: 20100613 17:00:00
Now: 20170920 00:59:00
Status: Public
H  Random intersection
Time Limit: 40s
Memory Limit: 128MB
Submissions: 142 Solved: 37
 Description
 There are N segments on the plane.
You are to find out how many pairs of segments intersect with each other.
A pair of segments intersect with each other if and only if they have at least one common point.
 Input
 the first line contains a single integer T  the number of the testcases
then T testcases are followed
each testcase contains an integer N( N <= 100000), the number of segments
then N lines are followed, each line contains 4 floating point numbers:
x1 y1 x2 y2
which means the coordinates of the two ends of a segment
for more details, see the sample input
(the input data is generated randomly, and the probability of a pair of segments intersecting is about 0.001)
 Output
 for each testcase, print 1 line with the number of the pairs of segments intersect with each other.
 Sample Input

3
3
0.0000 0.0000 1.0000 2.0000
0.0000 1.0000 1.0000 0.0000
0.0000 2.0000 1.0000 1.0000
4
0.0000 0.0000 0.0000 1.0000
0.0000 0.0000 1.0000 0.0000
0.0000 0.0000 0.0000 1.0000
0.0000 0.0000 1.0000 0.0000
2
0.0000 0.0000 1.0000 1.0000
0.0000 0.0000 2.0000 2.0000
 Sample Output

2
6
1
 Hint
 Source
 Hust Monthly 10.06.13/Li ZHANG