문제 138
최소 포함원과 두 점 세 점의 원
평면 위의 원에 관한 다음 질의를 처리해 보자.
- $\texttt{E}\ N$: 이어서 주어지는 $N$개의 점을 모두 포함하는 반지름이 가장 작은 원을 구한다.
- $\texttt{D}\ a_x\ a_y\ b_x\ b_y$: 두 점 $(a_x,a_y)$와 $(b_x,b_y)$를 지름의 양 끝점으로 하는 원을 구한다.
- $\texttt{T}\ a_x\ a_y\ b_x\ b_y\ c_x\ c_y$: 세 점 $(a_x,a_y)$, $(b_x,b_y)$, $(c_x,c_y)$를 모두 지나는 원을 구한다.
T 질의의 세 점은 한 직선 위에 있지 않다. E 질의에서 점이 하나뿐이면 그 점을 중심으로 하는 반지름이 $0$인 원을 답으로 한다. 점이 없다면 중심이 $(0,0)$이고 반지름이 $0$인 원을 답으로 한다.
입력
첫 번째 줄에 질의의 수를 의미하는 정수 $Q$가 주어진다. $(1\le Q\le100\,000)$
각 질의는 다음과 같이 주어진다.
E질의의 첫 번째 줄에 문자E와 정수 $N$이 공백으로 구분되어 주어진다. $(0\le N\le200\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 각 점의 정수 좌표 $x$, $y$가 공백으로 구분되어 주어진다. $(\lvert x\rvert\le10\,000; \lvert y\rvert\le10\,000)$D질의는 문자D와 정수 좌표 $a_x$, $a_y$, $b_x$, $b_y$가 공백으로 구분되어 한 줄에 주어진다. $(\lvert a_x\rvert,\lvert a_y\rvert,\lvert b_x\rvert,\lvert b_y\rvert\le10\,000)$T질의는 문자T와 정수 좌표 $a_x$, $a_y$, $b_x$, $b_y$, $c_x$, $c_y$가 공백으로 구분되어 한 줄에 주어진다. $(\lvert a_x\rvert,\lvert a_y\rvert,\lvert b_x\rvert,\lvert b_y\rvert,\lvert c_x\rvert,\lvert c_y\rvert\le10\,000)$
모든 질의에서 주어지는 점의 수의 합은 $200\,000$ 이하이다. D 질의는 $2$개, T 질의는 $3$개의 점으로 센다.
출력
각 질의에 대해 원의 중심의 $x$좌표, $y$좌표와 반지름을 공백으로 구분하여 한 줄에 출력한다.
반지름의 오차와 점의 포함 여부는 절대 오차 $10^{-6}$ 또는 상대 오차 $10^{-8}$를 기준으로 검사한다.
예제 입력 1
5 E 0 E 1 3 4 D 0 0 4 0 T 0 0 4 0 0 4 E 4 -1 -1 1 -1 1 1 -1 1
예제 출력 1
0.000000000000 0.000000000000 0.000000000000 3.000000000000 4.000000000000 0.000000000000 2.000000000000 0.000000000000 2.000000000000 2.000000000000 2.000000000000 2.828427124746 0.000000000000 0.000000000000 1.414213562373