Great Farmer Kim Sanghyuk
Time limit2sMemory limit1024 MB
Choose a radius r to maximize the daily profit from crops inside the circle (each worth wi times its distance to the boundary) minus the management cost A*r^2.
- Level
Hard8 of 10
- Topics
- Geometry, Math, Implementation, Greedy
- Solved
- No attempts yet
Problem
To become a rich farmer, Sanghyuk settled in a wasteland in a foreign country. Sanghyuk planted N crops in the wasteland. These crops are remarkable: give them water and they can be harvested every day.
Only after planting the N crops did Sanghyuk start planning to clear the wasteland into farmland. Think of the wasteland as a two-dimensional plane. Sanghyuk decided to clear all wasteland within radius r centered at (0, 0). Managing this cleared farmland costs A × r2 dollars every day.
Each crop i is planted at (xi, yi) and has value wi. Nothing can be harvested from a crop planted in the wasteland. A crop lying on the boundary of the farmland can also be harvested. The yield of a crop planted in the farmland is computed as follows.
If the shortest distance from the crop to the farmland boundary is ci, then each crop yields wi × ci dollars every day.
The example above shows the crops and the farmland on a two-dimensional coordinate plane. The green circle (r = 3) is the farmland boundary. The numbers under the crops are their values. Crops outside the farmland are in the wasteland, so they are not harvested.
For the crop with value 30, the shortest distance to the farmland boundary is shown by the red line segment, and its value is given below to two decimal places. In this configuration, with A = 10, the management cost is 10 × 3 × 3 = 90, and the total profit from the crops is about 113.058936. So Sanghyuk's profit here is about 23.058936 dollars. (This is not the maximum profit.)
Given A and the coordinates and values of the crops, determine the r that maximizes Sanghyuk's profit, taking the farmland management cost and the total crop yield into account.
Input
The first line gives the integers N and A. (1 ≤ N ≤ 105, 1 ≤ A ≤ 103)
From the second line to the N + 1-th line, each line gives the integers xi, yi, wi. (−103 ≤ xi, yi ≤ 103, 1 ≤ wi ≤ 200)
Output
Print the maximum profit (in dollars) that Sanghyuk can obtain by clearing the wasteland. If clearing nothing at all gives the maximum profit, print 0.
The answer is correct only if the relative or absolute error is within 10−6.