태양 에너지

시간 제한9초메모리 제한1024 MB

요약

각 별이 발사 각도에 따라 잘린 삼각형 모양의 에너지를 주는 상황에서 총합을 최대로 만드는 발사 각도를 찾는다.

난이도: 어려움10점 중 8점
유형: 기하, 정렬, 누적 합, 이분 탐색
정답자: 아직 제출이 없습니다

문제

당신은 생명체가 살 수 있는 행성을 찾기 위해 성간 우주를 여행할 계획이다. 우주선의 태양 전지판으로 충전할 수 있는 별 $N$ 개를 이미 찾아 두었다. 이제 우주선의 방향을 정해 이동 거리를 최대로 만드는 일만 남았다.

우주는 2차원 평면으로 모델링되며, 지구는 원점에 있다. 우주선은 지구에서 임의의 방향으로 직선을 따라 발사할 수 있다. 별 $i$ 는 우주선을 $x$ 축과 각도 $a_i$ 로 발사하면 $T_i$ 만큼 이동할 수 있는 에너지를 공급한다. 각도가 정확히 일치하지 않으면 우주선은 에너지를 덜 받는다. 구체적으로, 발사 방향이 $x$ 축과 각도 $a$ 를 이룰 때 별 $i$ 는

[\max(0, T_i - s_i \cdot \mathrm{dist}(a_i, a))]

만큼 이동할 수 있는 에너지를 공급한다. 여기서 $\mathrm{dist}(a,b)$ 는 각도 $a$ 에서 $b$ 로 가는 데 필요한 최소 라디안이다. 우주선이 이동할 수 있는 거리는 각 별이 공급하는 거리의 합이다. 우주선이 이동할 수 있는 최대 거리 $T$ 를 구하시오.

입력

첫째 줄에 $N$ 이 주어진다. $1\le N\le 10^5$ . 다음 $N$ 개 줄에는 각각 세 개의 실수 $T_i$ , $s_i$ , $a_i$ 가 주어진다. $0<T_i\le 1\,000$ , $0\le s_i\le 100$ , $0\le a_i < 2\pi$ . 입력의 모든 실수는 소수점 아래 자릿수가 최대 $6$ 자리이다.

출력

우주선이 이동할 수 있는 최대 거리를 한 줄에 출력한다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정된다.

예제2

예제 1
입력
```
2
100 1 1
100 1 1.5
```
예상 출력
```
199.500000
```

예제 2

입력

4
100 1 0.5
200 1 1
100 0.5 1.5
10 2 3

예상 출력

405.500000