ZOJ Problem Set - 3337
After a period of hard-working, 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:
, where E is the illumination of the point, I is the luminous intensity of the source, R is the distance between the source and the point and i is the angle between the normal of the plane and the light to the point.
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 xi, yi, hi and wi, indicating the coordinates of the i-th outlet box and the weight that it can afford. (-100 <= xi, yi <= 100, 0 < hi <= 100, 0 < wi <= 1000000) Each outlet box can connect only one light bulbs whose weight doesn't exceed wi 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 Ii, Mi and Ci, indicating the luminous intensity, the weight and the cost of the i-th light bulb. (0 < Ii <= 32768, 0 < Mi, Ci <= 1000000, ) Assume that the desk is always placed at the original point.
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.
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
0.354 10 0.000 0 1.000 10 2.000 20
Author: GUAN, Yao and OUYANG, Jialin
Source: ZOJ Monthly, May 2010