Moocast

시간 제한2초메모리 제한512 MB

요약

소마다 좌표와 전파 반경이 주어질 때, 단방향으로 도달할 수 있는 소의 수가 가장 많은 시작 소를 찾는다.

난이도: 보통10점 중 4점
유형: 그래프, DFS, 기하
정답자: 아직 제출이 없습니다

문제

농부 존의 소 $N$ 마리( $1 \le N \le 200$ )가 중요한 소식을 서로 알리려고 긴급 방송망을 만들려 한다.

먼 거리에서 서로 음메 하고 부르는 대신, 소들은 무전기를 한 대씩 갖추기로 했다. 무전기마다 신호가 닿는 거리에 한계가 있어서, 출력이 $P$ 인 무전기는 거리가 $P$ 이하인 소에게만 신호를 보낸다. 출력은 소마다 다르므로 소 A가 소 B에게 신호를 보내도 소 B는 소 A에게 보내지 못할 수 있다. 다행히 소들은 여러 마리를 거쳐 소식을 중계할 수 있어서, 모든 소가 다른 모든 소에게 직접 신호를 보낼 필요는 없다.

이렇게 신호가 한쪽으로만 닿을 수 있으므로, 중계까지 고려하면 어느 소에서 방송을 시작하느냐에 따라 소식을 받는 소의 수가 달라진다. 한 마리에서 시작한 방송이 닿는 소의 최대 마릿수를 구하라.

두 소 사이의 거리는 유클리드 거리다.

입력

첫째 줄에 $N$ 이 주어진다.

다음 $N$ 개의 줄에는 소 한 마리의 $x$ 좌표와 $y$ 좌표, 그 소가 가진 무전기의 출력 $p$ 가 순서대로 주어진다. 세 값은 모두 0 이상 25,000 이하의 정수다.

출력

한 마리에서 시작한 방송이 닿는 소의 최대 마릿수를 한 줄에 출력한다. 방송을 시작한 소도 이 수에 포함한다.

예제6

예제 1
입력
```
4
1 3 5
5 4 3
7 2 1
6 1 1
```
예상 출력
```
3
```
예제 2
입력
```
1
25000 25000 0
```
예상 출력
```
1
```
예제 3
입력
```
5
7 7 0
7 7 0
7 7 0
7 7 0
7 7 0
```
예상 출력
```
5
```
예제 4
입력
```
4
0 0 1
1 0 1
2 0 1
3 0 1
```
예상 출력
```
4
```
예제 5
입력
```
3
0 0 10
10 0 10
20 0 1
```
예상 출력
```
3
```
예제 6
입력
```
2
0 0 5
3 4 5
```
예상 출력
```
2
```