Oobleck 키우기

Oobleck은 신기한 마법 물질이다. 햇빛에 두면 끝없이 커지는 원 모양으로 자란다. 두 원이 닿으면 두 원은 하나로 합쳐진다. 합쳐진 원의 넓이는 두 원 넓이의 합과 같고, 중심은 원래 두 중심의 중점에 놓인다. 새 원의 확장 속도는 충돌한 두 원 중 더 큰 속도와 같다. 예시는 그림 F.1과 F.2에 나와 있다.

그림 F.1: 원 A는 중심 $(10,10)$, 반지름 $6$, 넓이 $36\pi$이다. 원 B는 중심 $(24,10)$, 반지름 $8$, 넓이 $64\pi$이다.

그림 F.2: 합쳐진 뒤 두 원은 중심 $(17,10)$, 반지름 $10$, 넓이 $100\pi$인 원 C로 바뀐다.

새로 만들어진 원은 기존의 다른 원과 교차해 합쳐짐이 연쇄적으로 일어날 수 있다. 교차 한 번에 하나 이상의 병합이 뒤따르는 이 과정을 ooblection이라고 부른다. ooblection은 처음 교차하는 순간에 즉시 일어나며, 그 안에 여러 번의 병합이 이어질 수 있다. 세 개 이상의 원이 한 번의 병합에 관여하면, 결과 원의 중심은 관여한 모든 원 중심의 평균이고 넓이는 관여한 원 넓이의 합이다. ooblection 후 최종 원의 확장 속도는 관여한 원 중 가장 큰 속도이다.

그림 F.3: 다섯 개 원의 ooblection.

그림 F.3은 다섯 개 원의 ooblection으로, 두 번째 샘플에서 설명한다. 시각 $t=1$에 원들은 그림 F.3a의 상태까지 커진다. 그때 원 A와 B가 합쳐져 원 F가 된다(그림 F.3b). 원 F는 원 C, D와 교차해 합쳐져 원 G가 된다(그림 F.3c). 마지막으로 원 G가 원 E와 교차해 최종 원 H를 만든다(그림 F.3d). 이 모든 과정은 시각 $t=1$에 일어난다. 원 H의 확장 속도는 원 A부터 E까지의 최대 확장 속도와 같다. 샘플 입력 2의 값에서 이 최대 속도는 2이다.

원들이 계속 커지면 결국 모든 원이 하나의 원으로 ooblect 된다. 그 원이 만들어지는 순간의 위치와 넓이를 구하라.

첫 줄에 양의 정수 $n$ ($n \leq 100$)이 주어진다. 원의 개수이다. 이어서 $n$개의 줄마다 $x$, $y$, $r$, $s$ 네 개의 수가 주어진다. $x$와 $y$ ($-10^9 \le x,y \le 10^9$)는 원의 중심 좌표이다. $r$ ($1 \leq r \leq 10^6$)은 초기 반지름이고, $s$ ($1 \leq s \leq 10^6$)는 확장 속도이다. 입력의 어떤 두 원도 서로 닿아 있지 않다. 같은 시각에 시작되는 ooblection은 최대 하나이며, 각 ooblection은 정확히 두 원이 닿는 것으로 시작한다.

두 줄을 출력한다. 첫 줄에는 최종 원이 만들어지는 순간의 중심 $x$와 $y$를 출력한다. 둘째 줄에는 그 원의 반지름을 출력한다. 상대 오차나 절대 오차가 $10^{-6}$ 이내이면 정답으로 인정한다.