SOJ ONLINE JUDGE

문제 144

원에 그은 접선의 접점

내 상태
미제출
난이도
144번 문제 난이도 보기
Platinum IV
출제자
rlatjwls7882
시간 제한
5000 ms
메모리 제한
1024 MB
144번 문제 태그 보기
구현

평면 위의 점과 원에 대해 다음 질의를 처리해 보자.

  • $\texttt{P}\ a_x\ a_y\ r\ p_x\ p_y$: 점 $P=(p_x,p_y)$에서 중심 $A=(a_x,a_y)$, 반지름 $r$인 원에 그을 수 있는 접선의 접점을 모두 구한다.
  • $\texttt{C}\ a_x\ a_y\ r\ b_x\ b_y\ s$: 중심 $A=(a_x,a_y)$, 반지름 $r$인 원과 중심 $B=(b_x,b_y)$, 반지름 $s$인 원의 공통접선의 접점 쌍을 모두 구한다.

점이 원 위에 있다면 그 점을 접점 하나로 센다. 두 원이 완전히 같으면 공통접선은 무한히 많다. 같은 접선을 중복해서 세지 않는다.

입력

첫 번째 줄에 질의의 수를 의미하는 정수 $Q$가 주어진다. $(1\le Q\le100\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 질의가 다음 형식 중 하나로 주어진다.

  • 문자 P와 정수 $a_x$, $a_y$, $r$, $p_x$, $p_y$가 공백으로 구분되어 주어진다. $(-1\,000\le a_x,a_y,p_x,p_y\le1\,000; 1\le r\le1\,000)$
  • 문자 C와 정수 $a_x$, $a_y$, $r$, $b_x$, $b_y$, $s$가 공백으로 구분되어 주어진다. $(-1\,000\le a_x,a_y,b_x,b_y\le1\,000; 1\le r,s\le1\,000)$

출력

각 질의에 대해 첫 번째 줄에 접선의 수 $K$를 출력한다. 접선이 무한히 많으면 $-1$만 출력한다.

접선이 유한 개이면 두 번째 줄부터 $K$개의 줄에 걸쳐 접선마다 다음 값을 공백으로 구분하여 출력한다.

  • P 질의: 접점의 좌표 $x$, $y$
  • C 질의: 첫 번째 원의 접점의 좌표 $x_1$, $y_1$과 두 번째 원의 접점의 좌표 $x_2$, $y_2$

접선의 출력 순서는 자유이며, 같은 접선을 중복해서 출력하면 안 된다. 두 원이 접하면 한 접선의 두 접점이 같을 수 있다.

출력한 점의 원까지의 거리, 접선의 수직 조건, 공통접선과 원 중심까지의 거리 오차는 각각 $10^{-6}$ 미만이어야 한다.

예제 입력 1

7
P 0 0 1 2 0
P 0 0 1 1 0
P 0 0 1 0 0
C 0 0 1 3 0 1
C 0 0 1 2 0 1
C 0 0 1 1 0 2
C 0 0 1 0 0 1

예제 출력 1

2
0.500000000000 0.866025403784
0.500000000000 -0.866025403784
1
1.000000000000 0.000000000000
0
4
0.000000000000 -1.000000000000 3.000000000000 -1.000000000000
0.000000000000 1.000000000000 3.000000000000 1.000000000000
0.666666666667 -0.745355992500 2.333333333333 0.745355992500
0.666666666667 0.745355992500 2.333333333333 -0.745355992500
3
0.000000000000 -1.000000000000 2.000000000000 -1.000000000000
0.000000000000 1.000000000000 2.000000000000 1.000000000000
1.000000000000 0.000000000000 1.000000000000 0.000000000000
1
-1.000000000000 0.000000000000 -1.000000000000 0.000000000000
-1

제출

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