시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 518 | 103 | 71 | 23.355% |
무선 센서 네트워크는 여러 개의 센서로 구성된 네트워크를 의미한다. 각 센서는 센서가 위치한 곳의 온도, 소리, 기압 등을 조사한다.
홍준이는 아마존 이산화탄소 측정 단체(Amazon Carbon-dioxide Measurement, 약칭 ACM)에서 프로젝트를 하나 맡았다. 그 프로젝트는, 아마존에 있는 무선 센서 네트워크로 부터 얻은 탄소의 양을 알아내어 최근 10년 동안 국제 화석 연료 사용양을 구한다. 그 사용량은 세계 산소 전달에 중요한 역할을 한다. 아마존의 숲은 매우 커서 홍준이의 역할이 중요하다.
센서들은 유클리드 거리 d 안에 있는 센서들과 통신할 수 있다. 홍준이는 2차원 평면에서 n개의 센서에 대한 좌표가 주어졌을 때, 집합안에 있는 센서들이 서로 직접적으로 통신 가능한 집합의 최대 크기와 그 집합을 구해야 한다.
입력의 첫 줄에는 센서의 개수 n과 센서끼리 직접적으로 통신 가능한 거리 d가 주어진다 (1 ≤ n ≤ 100, 1 ≤ d ≤ 10 000). 센서들의 번호는 1번 부터 n번까지 순서대로 매겨져 있고, 다음 n개의 줄에 센서 번호 순서대로 좌표 x, y가 주어진다 (-10 000 ≤ x, y ≤ 10 000).
첫 줄에 집합 내에 있는 센서들끼리 서로 직접적으로 통신할 수 있는 집합의 최대 크기를 출력하고, 둘째 줄에 그 집합에 있는 센서들의 번호를 출력한다. 만약, 가능한 답이 여러 가지인 경우 그 중 아무거나 하나 출력한다.
4 1 0 0 0 1 1 0 1 1
2 1 2
ICPC > World Finals > ACM-ICPC World Finals 2014 I번