P7058 [NWRRC 2015] Kingdom Trip

从前有一个王国，由一位聪明的国王统治。在他统治的四十三年间，通过成功的军事行动和娴熟的外交手段，王国变成了一个无限平坦的二维平面。这样的形式极大地简化了旅行，因为没有边界。 王国计划举办一个盛大的节日。有 $n$ 个地点供人们聚集。国王希望能更近距离地观察他的子民，因此他下令在这些地点之间进行旅行。他希望在每个地点发表演讲。最初，他的旅行被设计为一个多边形链 $p$：$p_{1} \to p_{2} \to \ldots \to p_{n}$。 国王不仅聪明，而且年事已高。因此，他的助手们想出了一个主意，跳过一些地点，以便让国王尽可能少地发表演讲。新的旅行计划必须是由 $p$ 的某个子序列组成的多边形链：从 $p_{1}$ 开始，到 $p_{n}$ 结束，形式上为 $p_{i_{1}} \to p_{i_{2}} \to \cdots \to p_{i_{m}}$，其中 $1 = i_{1} < i_{2} < \cdots < i_{m} = n$。助手们知道，如果从 $p_{j}$ 到线段 $p_{i_{k}} \to p_{i_{k+1}}$ 的距离超过 $d$，对于这样的 $k$，即 $i_{k} < j < i_{k+1}$，国王不会允许跳过地点 $j$。 帮助助手们找到包含最少可能地点的新路线。

输入文件的第一行包含两个整数 $n$ 和 $d$——旅行初始计划中的地点数和允许跳过地点的最大距离 $(2 \le n \le 2000$；$1 \le d \le 10^{6})$。 接下来的 $n$ 行描述了旅行。第 $i$ 行包含两个整数 $x_{i}$ 和 $y_{i}$——点 $p_{i}$ 的坐标。坐标的绝对值不超过 $10^{6}$。没有两个点重合。

输出国王将访问的最少地点数。保证对于 $d \pm 10^{-4}$，答案是相同的。

时间限制：2 秒，内存限制：256 MB。 题面翻译由 ChatGPT-4o 提供。