왕국 순회

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

요약

첫 점부터 마지막 점까지 바로가기 구간에서 빠진 모든 점이 거리 d 안에 들도록 가장 짧은 부분 수열을 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 기하
정답자: 아직 제출이 없습니다

문제

어느 왕국은 국경이 없는 무한한 평면이다. 왕국에는 사람들이 모이는 장소가 $n$ 개 있다.

왕은 백성을 가까이서 보려고 이 장소를 모두 도는 순회를 계획했고, 장소마다 연설을 하기로 했다. 처음 계획한 경로는 꺾은선 $p_1 \to p_2 \to \cdots \to p_n$ 이다.

왕이 나이가 많은 탓에, 보좌관은 연설 횟수를 줄이려고 몇몇 장소를 건너뛰려 한다. 새 경로는 $p$ 의 부분수열로 이루어진 꺾은선이어야 하고, $p_1$ 에서 시작해 $p_n$ 에서 끝나야 한다. 즉 $1 = i_1 < i_2 < \cdots < i_m = n$ 을 만족하는 $p_{i_1} \to p_{i_2} \to \cdots \to p_{i_m}$ 꼴이다.

$i_k < j < i_{k+1}$ 인 장소 $p_j$ 는 $p_j$ 에서 선분 $p_{i_k} p_{i_{k+1}}$ 까지의 거리가 $d$ 이하일 때만 건너뛸 수 있다. 그 거리가 $d$ 를 넘으면 왕은 그 장소를 빼는 것을 허락하지 않는다.

원래 경로

새 경로

장소 수가 가장 적은 새 경로를 찾아라.

입력

첫 줄에 정수 $n$ 과 $d$ 가 주어진다 ( $2 \le n \le 2000$ , $1 \le d \le 10^6$ ). $n$ 은 처음 계획에 있는 장소의 수이고, $d$ 는 건너뛴 장소까지 허용하는 최대 거리이다.

다음 $n$ 개 줄에는 $i$ 번째 장소 $p_i$ 의 좌표 $x_i$ 와 $y_i$ 가 주어진다. 두 좌표의 절댓값은 $10^6$ 이하이고, 좌표가 같은 장소는 없다.

출력

왕이 방문하는 장소 수의 최솟값을 출력한다. $d$ 를 $10^{-4}$ 만큼 늘리거나 줄여도 답은 같음이 보장된다.

예제7

예제 1
입력
```
5 2
2 6
8 2
14 2
12 9
13 8
```
예상 출력
```
3
```

예제 2

입력

2 1
-1000000 -1000000
1000000 1000000

예상 출력

예제 3
입력
```
6 1
0 0
3 0
11 0
40 0
41 0
100 0
```
예상 출력
```
2
```
예제 4
입력
```
3 1
0 0
10 0
1 0
```
예상 출력
```
3
```

예제 5

입력

7 1000000
0 0
500000 -400000
-300000 200000
120000 900000
-900000 -900000
700000 700000
1000000 -1000000

예상 출력

예제 6

입력

예상 출력

예제 7

입력

41 300
100000 0
99923 3926
99692 7846
99307 11754
98769 15643
98079 19509
97237 23345
96246 27144
95106 30902
93819 34612
92388 38268
90814 41866
89101 45399
87250 48862
85264 52250
83147 55557
80902 58779
78532 61909
76041 64945
73432 67880
70711 70711
67880 73432
64945 76041
61909 78532
58779 80902
55557 83147
52250 85264
48862 87250
45399 89101
41866 90814
38268 92388
34612 93819
30902 95106
27144 96246
23345 97237
19509 98079
15643 98769
11754 99307
7846 99692
3926 99923
0 100000

예상 출력