All the Cuts
In a two dimensional plane, there are “R” red points, “B” blue points and “G” green points. These points are expressed as ordered pair (x, y), x being the abscissa and y being the ordinate. For red points, y > 0. For other points, y < 0. We will call CD a cut on AB if line segment AB intersects line segment CD where A is a red point, B is a blue point and C, D are green points. For a line segment AB there can be arbitrary number of cuts.
Let us define a function F(i, j) to be the number of ways there can be “i” cuts on line segment “j” where “j” is a line segment connecting a red point and a blue point as mentioned above. Again, let us define a function g(p, q, j) as:
g(p, q, j) = (F(p, j) - F(p+1, j) + F(p+2, j) - F(p+3, j) …….. upto F(q, j)) modulo (10^9 + 7)
Find the sum of g(p, q, j) for all “j” modulo (10^9 + 7).
The first line will contain integer T denoting number of test cases.
The next line will contain integer R denoting number of red points. Next R lines will contain two integer denoting the co-ordinate of the red points.
The next line will contain integer B denoting number of blue points. Next B lines will contain two integer denoting the co-ordinate of the blue points.
The next line will contain integer G denoting number of green points. Next G lines will contain two integer denoting the co-ordinate of the green points.
Next line will contain two integer denoting p and q.
1 <= sum of red points over all test cases <= 2000
1 <= sum of blue points over all test cases <= 2000
1 <= sum of green points over all test cases <= 2000
1 <= p <= q <= 10^8
For any point, -10^8 <= x, y <= 10^8.
For a single test case, there will not be any 3 points lying on same straight line.
Print one line for each test case denoting the answer. Check sample output for actual output format.
2 1 0 5 1 0 -500 3 -1 -1 1 -1 1 -2 1 2 1 0 5 2 0 -500 -1 -501 3 -1 -1 1 -1 1 -2 1 2
In the first test case, for segment AB joining point (0, 5) and (0, -500) there can be at most 2 cuts. So,
F(1, AB) = 2
F(2, AB) = 1
So, g(1, 2, AB) = F(1, AB) - F(2,AB) = 2 - 1 = 1
Since, in there can be only one segment joining red points and blue points g(1, 2, AB) is the answer.
In the second test case, there will be two segment for which we have to calculate function g. For both of them the value of function g is 1. So, the answer is 1 + 1 = 2.