성간 여행
시간 제한5초메모리 제한512 MB
각 별이 t - s*dist(a,b)만큼 기여할 때, 기여의 합을 최대로 만드는 발사 각도 b를 찾는 문제입니다.
문제
당신은 거주 가능한 행성을 찾기 위해 성간 공간을 여행하려 한다. 태양 전지판으로 우주선을 충전할 수 있는 별 n개를 이미 찾아냈다. 이제 남은 일은 우주선이 이동할 수 있는 거리를 최대로 만드는 방향을 정하는 것이다.
우주는 2차원 평면으로 모델링되며, 지구는 원점에 있다. 우주선은 지구에서 임의의 방향으로 직선을 따라 발사할 수 있다. 별은 우주선이 X축과 특정 각도를 이루며 발사될 때 일정 거리를 이동할 수 있는 에너지를 공급한다. 각도가 완전히 일치하지 않으면 우주선은 더 적은 에너지를 받는다.
각 별은 우주선이 X축과 각도 a로 발사될 때 이동할 수 있는 거리 t와, 각도가 a에서 벗어날수록 거리가 줄어드는 정도를 나타내는 배율 s를 가진다. 발사 방향이 X축과 각도 b를 이룰 때 우주선이 이동할 수 있는 거리는 다음과 같다.
max(0, t - s · dist[a, b])
여기서 dist[a, b]는 각도 a와 b 사이를 이동하는 데 필요한 최소 음이 아닌 라디안 값이다. 우주선이 이동할 수 있는 총 거리는 각 별이 기여하는 거리의 합이다.
별들이 우주선에 공급할 수 있는 최대 이동 거리를 구하라.
입력
첫 줄에 별의 개수 n (1 ≤ n ≤ 105)이 주어진다.
다음 n개 줄에는 각각 공백으로 구분된 세 실수
t (0.0 < t ≤ 1000.0) s (0.0 ≤ s ≤ 100.0) a (0.0 ≤ a < 2π)
가 주어진다. t는 해당 별의 에너지가 지원할 수 있는 최대 거리, s는 그 별의 감쇠 배율, a는 그 별의 에너지로 최대 거리를 얻을 수 있는 최적 각도이다.
출력
우주선이 이동할 수 있는 최대 거리를 실수 하나로 출력한다. 답은 절대 오차 또는 상대 오차 10-6 이내여야 한다.