RiseOJ – 음머캐스트

설명

농부 존의 소 $$N$$ 마리( $1 \leq N \leq 200$ )는 중요한 소식을 서로에게 방송하기 위한 비상 "음머캐스트(moo-cast)" 시스템을 조직하려고 한다.

먼 거리에서 서로 음머 하고 울부짖는 대신, 소들은 한 마리당 하나씩 무전기를 갖추기로 했다. 각 무전기는 전송 반경에 제한이 있어서, 출력이 $$P$$ 인 무전기는 거리 $$P$$ 이내에 있는 다른 소에게만 전송할 수 있다(소 A의 출력이 소 B의 출력보다 크면, 소 A는 소 B에게 전송할 수 있어도 소 B는 소 A에게 전송하지 못할 수 있다는 점에 유의한다). 다행히 소들은 여러 번의 중계를 거치는 경로를 따라 메시지를 전달할 수 있으므로, 모든 소가 다른 모든 소에게 직접 전송할 수 있을 필요는 없다.

무전기 전송의 비대칭적인 특성 때문에, 어떤 소의 방송은 (중계를 고려했을 때) 다른 소의 방송보다 더 많은 수신자에게 도달할 수 있다. 한 마리의 소에서 시작된 방송이 도달할 수 있는 소의 최대 마릿수를 구해 소들을 도와주자.

문제 출제: 브라이언 딘(Brian Dean)

제약

문제 출제: 브라이언 딘(Brian Dean)

입력 형식

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

다음 $$N$$ 개의 줄에는 각 소의 $$x$$ , $$y$$ 좌표( $0 \ldots 25,000$ 범위의 정수)와 그 소가 가진 무전기의 출력 $$p$$ 가 주어진다.

출력 형식

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

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 moocast.in · 출력을 쓸 파일 moocast.out

예제 1

입력

출력

설명

In the example above, a broadcast from cow 1 can reach 3 total cows, including
cow 1.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > December > Silver

올림피아드 > USACO > 2016-2017 > December > Silver

태그

JudgeUSACO

음머캐스트

평가 및 의견

풀이 제출