루미 알고리즘

#1414골드Saunas

PO 2017 결선코딩출제 Simon Lindholm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPoint valueBounds
121N ≤ 1000, all t are the same.
229N ≤ 1000, all a are positive (i.e., the Finns love extreme temperatures).
338N ≤ 1000, all a are negative.
412No 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

출처 표기

출처: Programmeringsolympiaden 2017년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.