SOJ ONLINE JUDGE

문제 138

최소 포함원과 두 점 세 점의 원

내 상태
미제출
난이도
138번 문제 난이도 보기
Platinum II
출제자
rlatjwls7882
시간 제한
4000 ms
메모리 제한
1024 MB
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

제출

편집기에서 나가려면 Esc를 누른 뒤 Tab 또는 Shift와 Tab을 누르세요.