Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

HS12CHSH - Cherries Sharing

no tags 

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.


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

NS 12.393005
NS 25.082539
WE 29.850876
WE 19.284767


By solving this problem you score 10 points.

Added by:kuszi
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:High School Programming League