Problem C
Cutting Cakes

Input: Standard Input

Output: Standard Output

 

Alice and Bob are twins. In their birthday, they have a really large cake of dimensions 104x104. The cake has a number of flowers on it. As usual, Alice and Bob starts playing with it. First, Alice cuts the cake in two pieces, and then Bob takes the part with the maximum flowers on it. Since, Alice likes the flowers too, she will try to get maximum number of flowers. The flowers, which are incident by the cut are ruined, and thus non of them get those. The badness of a cut is the difference of the number of flowers between the two sets.

 

The task presented to you is not to maximize the number of flowers, Alice gets. Instead, you are given the co-ordinates of the flowers, and a cut, made by Alice. You need to find out the number of flowers, that are partitioned into two parts, and the number of flowers, being ruined by the cut. Alice always cuts in a straight line.

 

Input

 

First line contains T, the number of test cases. Each test case starts with an integer N, the number of flowers. Following N lines each contains two integers, xi and yi, the co-ordinate of the i-th flower. No three flowers will be collinear. After that, a line with values, M, X1, Y1, X2, Y2, dX1, dY1, dX2, dY2 follows. Here, M is the number of queries. Each of these queries will be a line between two given points. The end points are generated by the function given below. Each call to the function generate will produce the end points of the query line. X1, Y1, X2, Y2, dX1, dY1, dX2, dY2 are used to generate the lines.

 

X1, Y1, X2, Y2, dX1, dY1, dX2, dY2

 

function generate

            X1 = (X1 + dX1) mod 104

            Y1 = (Y1 + dY1) mod 104

            X2 = (X2 + dX2) mod 104

            Y2 = (Y2 + dY2) mod 104

 

            if X1 == X2 and Y1 == Y2 then

                        Y2 = (Y1 + 1) mod 104

           

P.S.: It is highly unlikely that, an O(NM) solution would pass the time limits. You have to think of some more clever solution

 

 

 

 

 

 

Output

 

Each case starts with the line “Case #n:” where n is the number of the test case. For each line, output three integers, p, q and r; where r is the number of flowers on the line and p and q are the number of flowers on the sides of the line.

 

Constraints

 

l       

l       

l       

l        For all location of flower (xi,yi), . No three points will be collinear.

l       

l        All input values will fit into a 32bit signed integer

 

 

 

Sample Input                                                                               Output for Sample Input

1

4

5 5

5 10

10 5

10 10

2 -7 -7 7 7 1 1 1 1

Case #1:

1 1 2

1 1 2

 

 

 

Problem Setter: Manzurur Rahman Khan

Special Thanks: Sohel Hafiz