시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 1024 MB197660.000%

문제

좌표평면에 $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$는 정수

예제 입력 1

7
4 8 4
5 9 2
9 1 1
6 7 10
3 1 2
5 9 1
6 0 1

예제 출력 1

4

이 경우를 제외하고도 6번째 원에서 좌표평면으로 이동해도 최대값을 구할 수 있다.

예제 입력 2

8
8 8 7
10 6 4
4 5 1
1 0 1
6 7 10
3 9 1
10 6 1
-1 7 1

예제 출력 2

4

예제 입력 3

5
5 5 3
10 5 1
4 6 1
6 4 1
8 8 1

예제 출력 3

3

힌트

두 원의 위치관계

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

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

두 점에서 만난다. 한 점에서 만난다. 만나지 않는다.
외접 내접 외부에 있는 경우 내부에 있는 경우 동심원
$|r_A-r_B|<d<r_A+r_B$ $r_A+r_B=d$ $|r_A-r_B|=d$ $r_A+r_B<d$ $d<|r_A-r_B|$ $d=0$

두 점 사이의 거리

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

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

출처