#10412

Cutting Cake 45s 1024MB

Problems

Today is your and your twin sibling's birthday. To celebrate, you got a rectangular cake to share. The cake is decorated with \mathbf{N} 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 i⁠-⁠th patch of icing is \mathbf{A_i}, and your twin's is \mathbf{B_i}. If someone eats part of a patch, they get enjoyment proportional to the eaten area. For example, if you eat \frac{2}{3} of the area of the i⁠-⁠th icing patch, you would get \frac{2\mathbf{A_i}}{3} enjoyment from it. Note that there may be some flavors of icing that you or your twin do not enjoy, so the \mathbf{A_i} and/or \mathbf{B_i} values can be negative.

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 \mathbf{N} 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, \mathbf{T}. \mathbf{T} test cases follow. Each test case starts with a line containing three positive integers, \mathbf{N}, \mathbf{W}, and \mathbf{H}, 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) and the top-right corner is at (\mathbf{W}, \mathbf{H}). Then, a line describing the icing patch mold follows. This line contains four integers: \mathbf{P}, \mathbf{Q}, \mathbf{R}, and \mathbf{S}. The icing patch mold is a triangle with vertices at (0, 0), (\mathbf{P}, \mathbf{Q}), and (\mathbf{R}, \mathbf{S}). Then, \mathbf{N} lines follow. The i⁠-⁠th of these lines contains four integers \mathbf{X_i}, \mathbf{Y_i}, \mathbf{A_i}, and \mathbf{B_i}. The i⁠-⁠th patch is a triangle with vertices at (\mathbf{X_i}, \mathbf{Y_i}), (\mathbf{X_i} + \mathbf{P}, \mathbf{Y_i} + \mathbf{Q}), and (\mathbf{X_i} + \mathbf{R}, \mathbf{Y_i} + \mathbf{S}). You would get \mathbf{A_i} enjoyment from eating it and your twin would get \mathbf{B_i} enjoyment.

Output

For each test case, output one line containing Case #x: y/z, where x is the test case number (starting from 1) and \frac{y}{z} 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, z must be positive and of minimum possible value).

Example

4keyboard_return
1space_bar 5space_bar 5keyboard_return
3space_bar -1space_bar 2space_bar 2keyboard_return
1space_bar 2space_bar -10space_bar 5keyboard_return
2space_bar 100000000space_bar 50000000keyboard_return
80000000space_bar 0space_bar 40000000space_bar 40000000keyboard_return
5000001space_bar 2500000space_bar 500space_bar -501keyboard_return
15000000space_bar 5000000space_bar 501space_bar -400keyboard_return
2space_bar 10space_bar 10keyboard_return
0space_bar 2space_bar 4space_bar 2keyboard_return
2space_bar 2space_bar -4space_bar 5keyboard_return
4space_bar 6space_bar -6space_bar 5keyboard_return
3space_bar 622460462space_bar 608203753keyboard_return
486076103space_bar 36373156space_bar 502082214space_bar 284367873keyboard_return
98895371space_bar 126167607space_bar 823055173space_bar -740793281keyboard_return
26430289space_bar 116311281space_bar -398612375space_bar -223683435keyboard_return
46950301space_bar 278229490space_bar 766767410space_bar -550292032

Casespace_bar #1:space_bar 5/1keyboard_return
Casespace_bar #2:space_bar 288309900002019999899/320000000000000000keyboard_return
Casespace_bar #3:space_bar 37/4keyboard_return
Casespace_bar #4:space_bar 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 0 enjoyment. Your twin will eat all of the icing patch and receive 5 enjoyment from it. The absolute value of the difference between your and your twin's enjoyments is |0 - 5| = 5. In Sample Case #2, there are two icing patches. The optimal cut is at X = 15099999.99. Notice that the numerator and denominator of the answer can get very large. In Sample Case #3, there are two icing patches. The optimal cut is at X = 4. You will eat 75% of the first icing patch and receive -3 enjoyment from it. Your twin will eat 25% of the first icing patch and all of the second icing patch getting 5 \cdot 0.25 + 5 = 6.25 enjoyment. The absolute value of the difference between your and your twin's enjoyments is |-3 - 6.25| = 9.25 = \frac{37}{4}. Notice that cutting at X = 1 would give you 0 enjoyment and your twin 10 enjoyment. While both of those values are greater than the corresponding enjoyment when cutting at X = 4, the difference between them is 10 \gt 9.25, which means cutting at X = 4 is preferable anyway. In Sample Case #4, there are three icing patches. The optimal cut is at X \approx 521241077.6027.

Source

GCJ 2021wf A

#10412 upload 1 done 1 how_to_reg 1

Cutting Cake timer 45s memory 1024MB

Problems translate English text_fields