선박 충돌

좁고 제한된 수역에 있는 배에게는 다른 배들의 통행이 큰 위험 요소가 될 수 있다. 같은 구역에 통행량이 많을수록 충돌 위험도 커진다.

당신의 임무는 통행 상황을 관찰하여 충돌이 일어나기 전에 충돌 가능성이 높은 상황을 미리 감지하는 것이다. 각 배의 위치, 방향, 속도를 감지하는 센서가 있다. 방향과 속도가 일정하게 유지된다고 가정할 때, 배들 중 어느 하나라도 서로 충돌하게 될지 판단하라. 두 배가 주어진 거리 이내로 가까워지면 충돌한 것으로 본다.

첫째 줄에는 뒤따르는 테스트 케이스의 수를 나타내는 정수 $c$가 주어진다. 각 테스트 케이스는 두 수 $n$과 $r$이 있는 줄로 시작하는데, $n$은 배의 수, $r$은 충돌 거리이다. 두 배가 서로 $r$미터 이내로 가까워지면 충돌한 것으로 본다. 배의 수는 1000척을 넘지 않는다. 각 배는 네 수 $x$, $y$, $d$, $s$가 있는 줄로 표현된다. $x$와 $y$는 공통 원점으로부터 각각 동쪽과 북쪽으로의 거리로 배의 현재 위치를 나타내며, $-1000$ 이상 $1000$ 이하이다. 호수는 충분히 작아 평평한 평면으로 모델링할 수 있다. $d$는 배가 향하는 방향으로, 북쪽을 기준으로 시계 방향으로 잰 각도(도 단위)이다(따라서 동쪽은 $90$도이다). $s$는 배의 속도로 초당 미터(m/s) 단위이며, $0.001$ 이상 $1000$ 이하이다. $r$, $x$, $y$, $d$, $s$는 반드시 정수는 아니다. 입력 데이터는 $x$, $y$, $d$, $s$ 중 어느 값을 $10^{-6}$ 이하로 바꾸어도 정답이 달라지지 않도록 주어진다.

각 테스트 케이스마다, 배들 중 어느 하나라도 서로 $r$미터 이내로 가까워지기까지 걸리는 시간(초)을 가장 가까운 정수로 반올림하여 한 줄에 출력한다. 어떤 배도 서로 충돌하지 않는다면, 다음 줄을 출력한다.

No collision.