2019 North Central NA Regional Contest

Start

2019-11-09 18:00 UTC

2019 North Central NA Regional Contest

End

2019-11-09 23:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -203 days 22:06:18

Time elapsed

5:00:00

Time remaining

0:00:00

Problem K
Solar Energy

/problems/solarenergy/file/statement/en/img-0001.png

You are planning to travel in interstellar space in the hope of finding habitable planets. You have already identified $N$ stars that can recharge your spaceship via its solar panels. The only work left is to decide the orientation of the spaceship that maximizes the distance it can travel.

Space is modeled as a $2$D plane, with the Earth at the origin. The spaceship can be launched from the Earth in a straight line, in any direction. Star $i$ can provide enough energy to travel $T_ i$ distance if the spaceship is launched at an angle of $a_ i$ with the $x$-axis. If the angle is not perfectly aligned, then the spaceship gets less energy. Specifically, if the launch direction makes an angle of $a$ with the $x$-axis, then it gets enough energy to travel distance of

\[ \max (0, T_ i - s_ i \cdot \mathrm{dist}(a_ i, a)) \]

from star $i$, where $\mathrm{dist}(a,b)$ is the minimum radians needed to go from angle $a$ to $b$. The distance that the spaceship can travel is simply the sum of the distances that each star contributes. Find the maximum distance $T$ that the starship can travel.

Input

The first line contains the value $N$, $1\le N\le 10^5$. Following this are $N$ lines each containing three real numbers $T_ i$, $s_ i$, and $a_ i$, with $0<T_ i\le 1\, 000$, $0\le s_ i\le 100$, and $0\le a_ i < 2\pi $. All real numbers in the input have at most $6$ digits after the decimal point.

Output

On a single line output the maximum distance the spacecraft can travel. Your answer is considered correct if it has an absolute or relative error of at most $10^{-6}$.

Sample Input 1 Sample Output 1
2
100 1 1
100 1 1.5
199.500000
Sample Input 2 Sample Output 2
4
100 1 0.5
200 1 1
100 0.5 1.5
10 2 3
405.500000