문제 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