Today is your and your twin sibling’s birthday. To celebrate, you got a rectangular cake to share. The cake is decorated with NN triangular patches of icing (which may overlap). All the icing patches were created with the same triangular mold, so they have the same shape and orientation. Although you and your twin are very similar, your tastes in icing are much different. This difference is formalized by each of you having a different enjoyment value for each patch of icing. Specifically, your enjoyment value for eating the entire ii ⁠-⁠th patch of icing is AiAi , and your twin’s is BiBi . If someone eats part of a patch, they get enjoyment proportional to the eaten area. For example, if you eat 2323 of the area of the ii ⁠-⁠th icing patch, you would get 2Ai32Ai3 enjoyment from it. Note that there may be some flavors of icing that you or your twin do not enjoy, so the AiAi and/or BiBi values can be negative.

cutting cake codejam solution

For Solution

Click Here!

Today is your and your twin sibling’s birthday. To celebrate, you got a rectangular cake to share. The cake is decorated with NN triangular patches of icing (which may overlap). All the icing patches were created with the same triangular mold, so they have the same shape and orientation. Although you and your twin are very similar, your tastes in icing are much different. This difference is formalized by each of you having a different enjoyment value for each patch of icing. Specifically, your enjoyment value for eating the entire ii⁠-⁠th patch of icing is AiAi, and your twin’s is BiBi. If someone eats part of a patch, they get enjoyment proportional to the eaten area. For example, if you eat 2323 of the area of the ii⁠-⁠th icing patch, you would get 2Ai32Ai3 enjoyment from it. Note that there may be some flavors of icing that you or your twin do not enjoy, so the AiAi and/or BiBi values can be negative.

A cake with 4 icing patches.

You will cut the cake into two rectangular pieces by making a single vertical cut (parallel to the Y-axis). After cutting the cake, you will eat the left piece and your twin will eat the right piece. Your total enjoyment is the sum of the enjoyment you get from all icing to the left of the cut. Similarly, your twin’s enjoyment is the sum of the enjoyment they get from all icing to the right of the cut.

To be as fair as possible, you want to cut the cake such that the absolute value of the difference between your total enjoyment and your twin’s total enjoyment is as small as possible. Given the NN triangular icing patches on a rectangular cake, what is the minimum possible absolute value of the difference between your and your twin’s total enjoyments you can get?

Input

The first line of the input gives the number of test cases, TTTT test cases follow. Each test case starts with a line containing three positive integers, NNWW, and HH, representing the number of icing patches on the cake and the width and height of the top of the cake, respectively. The bottom-left corner of the cake is located at (0,0)(0,0) and the top-right corner is at (W,H)(W,H). Then, a line describing the icing patch mold follows. This line contains four integers: PPQQRR, and SS. The icing patch mold is a triangle with vertices at (0,0)(0,0)(P,Q)(P,Q), and (R,S)(R,S). Then, NN lines follow. The ii⁠-⁠th of these lines contains four integers XiXiYiYiAiAi, and BiBi. The ii⁠-⁠th patch is a triangle with vertices at (Xi,Yi)(Xi,Yi)(Xi+P,Yi+Q)(Xi+P,Yi+Q), and (Xi+R,Yi+S)(Xi+R,Yi+S). You would get AiAi enjoyment from eating it and your twin would get BiBi enjoyment.

Output

For each test case, output one line containing Case #xxyy/zz, where xx is the test case number (starting from 1) and yzyz is the minimum absolute value of the difference between your and your twin’s total enjoyment that can be achieved with a single vertical cut as an irreducible fraction (that is, zz must be positive and of minimum possible value).

Limits

Time limit: 45 seconds.
Memory limit: 1 GB.

Test Set 1 (Visible Verdict)

1T1001≤T≤100.
1N1001≤N≤100.
3W1093≤W≤109.
3H1093≤H≤109.
109Ai109−109≤Ai≤109, for all ii.
109Bi109−109≤Bi≤109, for all ii.
0P1090≤P≤109.
109Q109−109≤Q≤109.
0R1090≤R≤109.
109S109−109≤S≤109.
The three vertices of the mold (0,0)(0,0)(P,Q)(P,Q), and (R,S)(R,S) are not collinear.
The three vertices of each triangular icing patch are strictly inside the cake’s borders. Formally:
1XiWmax(P,R)11≤Xi≤W−max(P,R)−1, for all ii, and
max(0,Q,S)+1YiHmax(0,Q,S)1max(0,−Q,−S)+1≤Yi≤H−max(0,Q,S)−1, for all ii.

Sample

Sample Input
content_copy
4
1 5 5
3 -1 2 2
1 2 -10 5
2 100000000 50000000
80000000 0 40000000 40000000
5000001 2500000 500 -501
15000000 5000000 501 -400
2 10 10
0 2 4 2
2 2 -4 5
4 6 -6 5
3 622460462 608203753
486076103 36373156 502082214 284367873
98895371 126167607 823055173 -740793281
26430289 116311281 -398612375 -223683435
46950301 278229490 766767410 -550292032
Sample Output
content_copy
Case #1: 5/1
Case #2: 288309900002019999899/320000000000000000
Case #3: 37/4
Case #4: 216757935773010988373334129808263414106891/187470029508637421883991794137967

In Sample Case #1, there is a single icing patch. The optimal cut is to the left of the patch. You will eat no icing and receive 00 enjoyment. Your twin will eat all of the icing patch and receive 55 enjoyment from it. The absolute value of the difference between your and your twin’s enjoyments is |05|=5|0−5|=5.

The cake in the first sample with a single icing patch.
The cake in the first sample with a cut line at X = 4.5.

In Sample Case #2, there are two icing patches. The optimal cut is at X=15099999.99X=15099999.99. Notice that the numerator and denominator of the answer can get very large.

The cake in the second sample with 2 icing patches.
The cake in the second sample with a cut line at X = ~1.51e7.

In Sample Case #3, there are two icing patches. The optimal cut is at X=4X=4. You will eat 75% of the first icing patch and receive 3−3 enjoyment from it. Your twin will eat 25% of the first icing patch and all of the second icing patch getting 50.25+5=6.255⋅0.25+5=6.25 enjoyment. The absolute value of the difference between your and your twin’s enjoyments is |36.25|=9.25=374|−3−6.25|=9.25=374.

Notice that cutting at X=1X=1 would give you 00 enjoyment and your twin 1010 enjoyment. While both of those values are greater than the corresponding enjoyment when cutting at X=4X=4, the difference between them is 10>9.2510>9.25, which means cutting at X=4X=4 is preferable anyway.

The cake in the third sample with 2 icing patches.
The cake in the third sample with a cut line at X = 4.

In Sample Case #4, there are three icing patches. The optimal cut is at X521241077.6027X≈521241077.6027.

For Solution

Click Here!

Leave a Comment