HUST Monthly 2010.06.13

From: 2010-06-13 12:00:00 To: 2010-06-13 17:00:00 Now: 2017-09-20 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