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 |
Case #1: 1 1 2 1 1 2 |
Problem
Setter: Manzurur Rahman Khan
Special
Thanks: Sohel Hafiz