
ZOJ Problem Set  3337
After a period of hardworking, mildleopard become rich and could buy many light bulbs. He run wires around his house before he bought light bulbs. But he didn't consider the weights of the light bulbs until he went to buy the light bulbs. He wanted to select the light bulbs that could make the place where his desk placed had maximum illumination. What's more, he also wanted to minimize the cost because he knew that the money was not easy to earn.
Remember that the illumination from a source can be calculated by the following equation: Input The first line of the input contains an integer T (T <= 30), indicating the number of cases. The first lin of each test case contains two integers n and m, indicating the the number of light bulbs that mildleopard could connect in his house and that mildleopard could choose in the market. (1 <= n, m <= 100) Each of the next n lines contains four integers x_{i}, y_{i}, h_{i} and w_{i}, indicating the coordinates of the ith outlet box and the weight that it can afford. (100 <= x_{i}, y_{i} <= 100, 0 < h_{i} <= 100, 0 < w_{i} <= 1000000) Each outlet box can connect only one light bulbs whose weight doesn't exceed w_{i} and the coordinates of the light bulb will be the same as the outlet box. Then m lines follow, each of which contains three integers I_{i}, M_{i} and C_{i}, indicating the luminous intensity, the weight and the cost of the ith light bulb. (0 < I_{i} <= 32768, 0 < M_{i}, C_{i} <= 1000000, ) Assume that the desk is always placed at the original point. Output For each test case, output the maximum illumination mildleopard could get and the minimum cost to achieve it in one line. The maximum illumination should be a real number rounded to 0.001. Sample Input 4 1 1 1 0 1 100 1 100 10 1 1 1 0 1 100 1 101 10 1 2 0 0 1 100 1 100 10 1 100 20 1 2 0 0 1 100 1 100 10 2 100 20 Sample Output 0.354 10 0.000 0 1.000 10 2.000 20 Author: GUAN, Yao and OUYANG, Jialin Source: ZOJ Monthly, May 2010 