영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
Picture by SM (https://commons.wikimedia.org/wiki/File:Smoke_sauna.JPG) (cc-by-sa3.0)
Finns love to use saunas. It's actually not so strange. Sauna bathing feels good and usually takes place among good company.
However, problems often occur when there is company. The most important thing when one uses a sauna is that the temperature is set correctly. A Finn can be really fussy about a sauna's temperature. Different Finns have different maximum temperatures that they tolerate. If the temperature is too high for a particular Finn, that Finn will go home. Within the temperature range that a particular Finn can handle, that Finn has a different level of happiness depending on the temperature. A Finn's happiness follows a quadratic function (of the form ax^2 + bx + c).
A large number of Finns are using the sauna and they need your help. Can you find the maximum sum of the Finns' happiness if the sauna's temperature is set optimally? If the temperature is set higher than a Finn can tolerate, that Finn contributes nothing to the total happiness (they have gone home instead). The temperature is given in kelvin, with a lower bound of 0 K and an upper bound of 100000 K.
Input
The first line contains an integer 1 ≤ N ≤ 100000, which is the number of Finns. After that follow N lines, one per Finn. Each line contains four integers a, b, c, and t (-10^9 ≤ a,b,c ≤ 10^9, 1 ≤ t ≤ 100000), which represent that the Finn has happiness function ax^2 + bx + c, and can only handle temperatures between 0 K and t K, inclusive. The function is guaranteed to be positive over all values between 0 and t.
Output
Write out a single number: the largest possible happiness that can be achieved if the temperature is set correctly. The answer will be accepted if it has a relative or absolute error of at most 10^-5.
Points
Your solution will be tested on several test case groups. To get points for a group, your solution must pass all the test cases in the group.
| Group | Point value | Bounds |
| 1 | 21 | N ≤ 1000, all t are the same. |
| 2 | 29 | N ≤ 1000, all a are positive (i.e., the Finns love extreme temperatures). |
| 3 | 38 | N ≤ 1000, all a are negative. |
| 4 | 12 | No additional constraints. |
Explanation of example 1
In this case the optimal temperature is 0 K. Both Finns have the same happiness in this case: 1 · 0^2 - 6 · 0 + 10 = 10. Their total happiness is 10 + 10 = 20.
Explanation of example 2
In this case the optimal temperature is 10/3 K. The first Finn's happiness is -3(10/3)^2 + 20 · 10/3 + 3 = -100/3 + 200/3 + 3 = 36 + 1/3. The second Finn in this case goes home, because the temperature is too high (she only tolerates temperatures up to 1 K). The total happiness is therefore 36 + 1/3.
예제
예제 1
2 1 -6 10 4 1 -6 10 7
20.0000000000
예제 2
2 -3 20 3 5 -1 0 2 1
36.3333333333
예제 3
1 1000000 2 3 10000
100000000020003.0000000000