1233 . A really boring problem
Description
On a X-Y plane, there are N points and M line segments.
The coordinate of points and end points of line segments are real number X-Y sets.
Given the point index A and B, how many line segments intersect with the straight line going through points A and B ?
Lines are considered intersected iff they "touch" each others.
The will now be any points or end points located at the same coordinate.
Input Format
The input file starts with T, the number of cases.
For each case, the first line consist of M N Q, which indicate:
M - the number of line segments
N - the number of points
Q - the number of questions
The next M lines consist of 4 real numbers each, which means the coordinates of the end points of line segments, x1 y1 x2 y2.
The next M lines consist of 2 real numbers indicate the coordinate of points, x y.
The last Q lines contains (A,B) pairs.
The points are indexed from 0 to N-1.
Restrictions:
T = 10
0 < N,M ≤ 1000
0 < Q ≤ 1000000
-10000.0 ≤ x,y,x1,y1,x2,y2 ≤ 10000.0
Output Format
For each of the question, you should output the number of line segments which intersects with the straight line going through points A and B.
Sample Input 1
1 3 5 3 0.0 1.0 1.0 0.0 0.0 2.0 2.0 0.0 0.0 3.0 0.0 1000.0 0.0 0.0 1.0 1.0 2.0 2.0 3.0 3.0 -3.0 3.0 0 2 3 4 1 3
Sample Output 1
2 1 2
Hints
Problem Source
Migrated from old NTUJ.
pP
Subtasks
| No. | Testdata Range | Score |
|---|