P7058 [NWRRC 2015] Kingdom Trip

题目描述

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}.$ ![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/11476/1.png) Original route ![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/11476/2.png) New route Help the assistants to find the new route that contains the minimum possible number of locations.

输入格式

输出格式

说明/提示

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