시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 113 17 16 25.397%

문제

무선 센서 네트워크는 여러 개의 센서로 구성된 네트워크를 의미한다. 각 센서는 센서가 위치한 곳의 온도, 소리, 기압 등을 조사한다.

홍준이는 아마존 이산화탄소 측정 단체(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

힌트

출처

ACM-ICPC > World Finals > 2014 World Finals I번