题目描述

Once upon a time, there was a kingdom ruled by a wise king. After forty three years of his reign, by means of successful military actions and skillful diplomacy, the kingdom became an infinite flat two-dimensional surface. This form of the kingdom greatly simplified travelling, as there were no borders.

A big holiday was planned in the kingdom. There were $n$ locations for people to gather. As the king wanted to have a closer look at his people, he ordered to make a trip through these locations. He wanted to give a speech in each of these locations. Initially his trip was designed as a polygonal chain $p$ : $p_{1} \to p_{2} \to$ . . . $\to p_{n}.$

Not only the king was wise, but he was old, too. Therefore, his assistants came up with an idea to skip some locations, to make the king to give as few speeches as possible. The new plan of the trip has to be a polygonal chain consisting of some subsequence of $p$ : starting at $p_{1}$ and ending at $p_{n},$ formally, $p_{i_{1}} \to p_{i_{2}} \to · · · \to p_{i_{m}},$ where $1 = i_{1} < i_{2} < · · · < i_{m} = n$ . Assistants know that the king wouldn't allow to skip location $j$ , if the distance from $p_{j}$ to segment $p_{i_{k}} \to p_{i_{k+1}}$ exceeds $d$ , for such $k$ , that $i_{k} < j < i_{k+1}.$

Original route

New route

Help the assistants to find the new route that contains the minimum possible number of locations.

输入格式

The first line of the input file contains two integers $n$ and $d$ -- the number of locations in the initial plan of the trip and the maximum allowed distance to skipped locations $(2 \le n \le 2000$ ; $1 \le d \le 10^{6}).$

The following $n$ lines describe the trip. The i-th of these lines contains two integers $x_{i}$ and $y_{i}$ -- coordinates of point $p_{i}.$ The absolute value of coordinates does not exceed $10^{6}.$ No two points coincide.

输出格式

Output the minimum number of locations the king will visit. It is guaranteed that the answer is the same for $d ± 10^{−4}.$

题目大意

题目描述

很久以前，一位明智的国王统治着一个王国。在他长达43年的统治后，通过成功的军事行动和熟练的外交技巧，这个王国变成了一个无限的平面二维曲面。因为没有边界，这种方式大大地简化了王国的出行。

王国内准备举行一个盛大的节日。人们能聚集在$n$个地点。因为国王想要近一点地看到他的子民，所以他下令去这些地点旅行。他想在每个地点演讲。起初他的旅行被计划成了一串多边形链$P$:从$P_1$到$P_n$。

国王虽然很明智，但他也已经老了。因此，他的助手想出了一个方法来跳过部分地点，来确保国王演讲的次数能尽可能地少。旅程的新计划需要是一串由某个子序列所构成的多边形链$P$:从$P_1$到$P_n$，正规的表示为：从$P_{i_1}$到$P_{i_m}$，且$1=i_1<i_2<...<i_m=n$。国王的助手知道国王不会允许跳过地点$j$，如果$P_j$与$P_{i_k}$到$P_{i_{k+1}}$这一段的距离超过了$d$，对于每个$k$，$i_k<j<i_{k+1}$。

输入

第一行，包含两个整数$n$和$d$，分别表示最初的路线的地点数和跳过地点被允许的距离的最大值（$2≤n≤2000$;$1 \le d \le 10^6$)

接下来$n$行，第$i$行包含两个整数$x_1$和$y_1$，表示点$P_i$的坐标。坐标的绝对值不超过$10^6$。不会出现两个点重合的情况。

输出

输出国王经过的地点数量的最小值，答案保证在$d \pm 10^{-4}$内；

时间限制：2秒，内存限制：256MB

5 2
2 6
8 2
14 2
12 9
13 8

3

提示

Time limit: 2 s, Memory limit: 256 MB.