센서 네트워크

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

요약

모든 쌍 사이의 거리가 d 이하인 가장 큰 센서 집합의 크기와 번호를 출력합니다.

난이도: 어려움10점 중 8점
유형: 백트래킹, 그래프, 기하
정답자: 아직 제출이 없습니다

문제

무선 센서 네트워크에서 각 센서는 유클리드 거리 $d$ 이내의 다른 센서와 직접 통신할 수 있다. $n$ 개 센서의 2차원 좌표가 주어질 때, 서로 직접 통신 가능한 센서들만으로 이루는 집합의 최대 크기와 그 집합을 구한다.

입력

첫 줄에 센서 개수 $n$ 과 통신 거리 $d$ ( $1 \le n \le 100$ , $1 \le d \le 10\,000$ )가 주어진다. 다음 $n$ 줄에 센서 번호 순서대로 좌표 $x$ , $y$ ( $-10\,000 \le x,y \le 10\,000$ )가 주어진다.

출력

첫 줄에 최대 집합 크기를 출력한다. 둘째 줄에 해당 센서 번호를 공백으로 구분하여 출력한다. 답이 여러 개면 아무거나 하나를 출력한다.

예제1

예제 1
입력
```
4 1
0 0
0 1
1 0
1 1
```
예상 출력
```
2
1 2
```