허블 우주 망원경

한 천체물리학자가 허블 우주 망원경으로 나선 은하인 안드로메다 은하를 관측한다. 그는 이 은하에 있는 별 $n$개의 움직임에 관심이 있다. 각 별은 망원경 사진 속에서 일정한 속도로 직선을 따라 움직인다. $n$개의 별 중 하나는 특별한 별로, 이름은 알파(alpha)이다. 그는 알파에서 나머지 $n - 1$개의 별까지의 거리 중 최댓값이 가장 작아지는 시각을 알고 싶어 한다.

사진은 2차원 직교 좌표평면으로 나타낼 수 있다. $S = \{s_0, s_1, \dots, s_{n-1}\}$을 $n$개의 별의 집합이라 하고, $s_0$을 별 알파라고 하자. 별 $s_i$는 시간 $t$에 따라 궤적 $p_i + t\,v_i$를 따라 움직인다. 여기서 $p_i = (x_i, y_i)$는 시각 $0$에서 $s_i$의 위치이고, $v_i = (a_i, b_i)$는 $s_i$의 속도 벡터이다. 별들은 실제로 충돌하지 않는다. 두 별이 한 점에서 만나더라도 서로를 그대로 통과한다.

별들과 그 속도가 주어질 때, $0 \le t \le 10^5$ 범위에서 알파부터 나머지 별들까지의 최대 거리가 최소가 되는 시각 $t$를 구하여라. 그런 시각이 여러 개라면 가장 이른 시각을 출력한다.

그림 1은 별이 $4$개인 예시를 보여 준다. 각 화살표는 별의 속도 벡터이다. 이 예시에서는 시각 $t = 3$일 때 알파에서 나머지 $3$개의 별까지의 최대 거리가 가장 작다.

(a) 시각 $t = 0$일 때, (b) 시각 $t = 3$일 때.

그림 1. 예시.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 별의 수를 나타내는 정수 $n$ ($2 \le n \le 50000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 네 정수 $x_i$, $y_i$, $a_i$, $b_i$가 주어지며, $(x_i, y_i)$는 시각 $0$에서 별 $s_i$의 위치이고 $(a_i, b_i)$는 그 속도 벡터이다 ($-200000 \le x_i, y_i \le 200000$, $-500 \le a_i, b_i \le 500$). 이 $n$개의 줄 중 첫째 줄이 알파($s_0$)를 나타낸다. 둘 이상의 별이 시각 $0$에서 같은 위치에 있을 수도 있다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 $0 \le t \le 10^5$ 범위에서 알파($s_0$)로부터 나머지 $n - 1$개의 별까지의 최대 거리가 최소가 되는 시각을 소수점 아래 넷째 자리까지 반올림하여 한 줄에 하나씩 출력한다.