별똥별에 소원을
시간 제한8초메모리 제한512 MB
반지름이 일정 비율로 줄어드는 움직이는 구들이 서로 닿으면 함께 사라질 때, 각 구가 사라지는 시간을 순서대로 구한다.
문제
수수께끼의 조직 JAG (Japanese Alumni Group)는 정기적으로 회의를 연다. 어느 날 의제는 "곧 열리는 ICPC (International Collegiate Programming Contest) 국내 예선에서 참가 팀이 실력을 발휘할 수 있도록 하려면 어떻게 할까"였다. 회의 결론은 별똥별에 각 팀의 건투를 비는 것이었고, 그들은 본부가 있는 건물 옥상에 올랐다.
옥상에 오르자 하늘에는 개의 별똥별이 보였다. 별똥별은 3차원 공간 위의 구로 표현되고, 부터 까지 번호가 붙어 있다. 별에 밝은 멤버에 따르면, 각 별똥별은 일정한 속도로 직선 이동하면서 동시에 일정한 속도로 반지름이 작아진다고 볼 수 있다. 실제로 측정해 보니 각 별똥별의 초기 위치 , 이동 속도 , 초기 반지름 , 소멸 속도 를 알 수 있었다. 이는 별똥별 가 시각 ()에 중심 좌표 , 반지름 인 구가 된다는 뜻이다. 별똥별은 반지름이 0이 되는 순간 자연 소멸한다. 또 두 별똥별이 접촉하면 두 별똥별 모두 소멸한다.
당신의 일은 참가 팀의 건투를 효율적으로 빌 수 있도록, 각 별똥별이 소멸할 때까지의 시간을 구하는 것이다. 그들 중에는 뛰어난 시력을 가진 사람이 있으므로, 주어진 개 외에 별똥별이 존재할 가능성은 고려하지 않아도 된다. 게다가 그들은 매우 효율적으로 별똥별을 관측했으므로 관측에 걸린 시간은 무시할 수 있을 만큼 작다고 생각해도 된다.
입력
입력은 여러 데이터 세트로 구성되며, 하나의 입력에 포함되는 데이터 세트의 수는 100 이하다. 각 데이터 세트의 형식은 다음과 같다.
...
은 별똥별의 수를 나타내는 정수이고, 이상 이하라고 가정해도 된다.
이어지는 줄에는 별똥별의 정보가 주어진다. 각 줄은 소수점 아래 4자리로 표현된 8개의 값을 포함하고, 는 별똥별 의 초기 위치를, 는 이동 속도를, 는 초기 반지름을, 는 소멸 속도를 나타낸다. 주어지는 값에 대해 , , , , , , , 이라고 가정해도 된다.
또한 주어지는 데이터 세트에 대해 다음을 가정해도 된다.
- 어떤 한 별똥별의 초기 반지름이 만큼 변해도 접촉하는 별의 쌍의 집합은 변하지 않는다.
- 어떤 한 별똥별이 접촉으로 소멸하지 않는다고 가정해도 이내의 시간에 둘 이상의 별똥별과 접촉하거나, 다른 별똥별과 접촉하는 시각으로부터 이내에 자연 소멸하지 않는다.
- 초기 상태에서는 어떤 두 별똥별도 겹쳐 있지 않고 이상 떨어져 있다.
- 시각 에서는 어떤 두 별똥별도 접촉하지 않는다.
은 입력의 끝을 나타낸다. 이는 데이터 세트에 포함하지 않는다.
출력
각 데이터 세트에 대해 각 별똥별이 소멸할 때까지의 시간을 별똥별 1부터 순서대로 각각 한 줄에 출력한다.
출력에는 을 초과하는 절대 오차가 있어서는 안 된다.
그 밖의 여분의 문자를 출력해서는 안 된다.