22946번 - 원 이동하기 1

좌표평면에 $N$개의 원이 존재한다.

$N$개의 원 중 임의의 두개의 원을 선택했을 때 내접, 외접 등 교점이 존재하지 않도록 존재한다. 하나의 원이 다른 원 안에 포함될 수는 있다.

하나의 원 내부에서 다른 원의 내부로 이동하려고 한다. 원 내부는 단 한 번만 방문 할 수 있으며 두 번 이상 방문을 할 수 없다.

문제 편의상 좌표평면을 원점이 (0, 0)이고 반지름이 무수히 큰 하나의 원이라고 가정하자.

좌표평면에 두 원 A, B만 존재한 상황에서 원 A 내부에서 원 B 내부로 올바르게 이동하는 경우는 아래와 같다.

1. 원 A와 원 B가 서로 포함관계가 아니고 만나지 않는 경우

첫 번째 경우는 원 A 내부 $\rightarrow$ 좌표평면 $\rightarrow$ 원 B 내부로 이동하였다. 이 경우를 제외한 올바른 경로는 존재하지 않는다.

2. 원 B가 원 A안에 존재하는 경우

두 번째 경우는 원 A 내부 $\rightarrow$ 원 B 내부로 이동하였다. 이 경우를 제외한 올바른 경로는 존재하지 않는다.

3. 원 A가 원 B안에 존재하는 경우

세 번째 경우도 원 A 내부 $\rightarrow$ 원 B 내부로 이동하였다. 이 경우를 제외한 올바른 경로는 존재하지 않는다.

아래 경우는 원 A 내부에서 원 B로 올바르게 이동하지 않은 경우들이다.

4. 좌표평면 위에 원 A, B, C가 존재하고 서로 포함관계가 아니면서 만나지 않는 경우

이 경우는 원 A 내부 $\rightarrow$ 좌표평면 $\rightarrow$ 원 C 내부 $\rightarrow$ 좌표평면 $\rightarrow$ 원 B 내부로 이동한 경로이다. 좌표평면을 2번 방문하였기 때문에 올바르게 이동한게 아니다.

4. 좌표평면 위에 원 A, B가 존재하고 원 B가 원 A의 내부에 있을 경우

이 경우는 원 A 내부 $\rightarrow$ 좌표평면 $\rightarrow$ 원 A 내부 $\rightarrow$ 원 B 내부로 이동한 경로이다. 원 A 내부를 2번 방문하였기 때문에 올바르게 이동한게 아니다.

좌표평면에서 임의의 두 원을 골랐을 때 하나의 원 내부에서 다른 원 내부로 이동할 때 방문한 원의 최대 개수를 구하시오.

첫 번째 줄에는 원의 개수 $N$이 주어진다.

두 번째 줄부터 $N + 1$번째 줄까지 원의 좌표 $x$, $y$와 반지름 $R$이 공백으로 구분되어 주어진다.

임의의 두 원을 선택했을 때 하나의 원에서 다른 원으로 이동할 때 방문한 원의 최대 개수를 출력한다.

• $2 ≤ N ≤ 5,000$
• $-1,000,000 ≤ x , y ≤ 1,000,000$
• $1 ≤ r ≤ 10,000$
• $x, y, r$는 정수

두 원의 위치관계

두 원의 위치관계를 파악할 때 아래를 이용하면 된다.

원 A의 반지름은 $r_A$, 원 B의 반지름은 $r_B$, 원 A와 원 B의 중심 사이의 거리를 $d$라고 가정하자.

두 점 사이의 거리

$(x_1, y_1)$와 $(x_2, y_2)$ 사이의 거리 $d$를 구하는 식은 아래와 같다.

$d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$