HS12CHSH - Cherries Sharing
Alice and Bob are trying to cut a rectangular cherry cake into two pieces.
They have agreed that:
- the partition must be done with a single, straight line cut parallel to one of the sides of the cake
- the cut should cross the center of mass of all cherries
- the number of cherries touched during the cut should be as small as possible
You have been asked to compute the parameters of the cut satisfying the above conditions. Simplify the problem assuming that each cherry is an ideal, homogeneous ball.
First, you are given T, the number of test cases (T<100). The test cases follow. Each of the test cases consists of three positive integers: w, l, c denoting the width, the length and the number of cherries in the cake (w, l < 100 and c<10000). In each of the next c lines the parameters of each successive cherry are given: x, y - the coordinates of the center), m - the mass of the cherry and r - the radius of the cherry (x<w, y<l, m, r <10). Assume that the cake's vertices are: (0, 0), (x, 0), (x, y), (0, y). The height of the cake and the vertical position of cherries have no impact on the cut parameters, hence they may be considered irrelevant and ignored.
For each of the test cases output in a separate line two characters: WE for a cut parallel to x-axis and NS for a cut parallel to y-axis and one number - the cut offset with six digits of precision.
Input: 2 31 71 5 10.5680 32.3080 8.0160 2.1860 15.9970 30.3860 2.7680 2.2490 3.6890 11.9840 7.9280 1.0350 6.5280 48.6800 5.7440 1.2970 23.5240 31.1280 9.6440 1.8320 69 36 5 15.0760 13.1800 5.9020 2.3240 33.5610 24.2980 7.9390 2.6720 27.4260 20.5670 2.5220 2.4220 38.7100 17.4060 1.7820 1.1920 20.8150 18.8790 9.0090 1.3320 Output: NS 12.393005 NS 25.082539
WE 29.850876 WE 19.284767
By solving this problem you score 10 points.