http://poj.org/problem?id=1328
Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.
We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.
http://blog.csdn.net/petercsj/article/details/4602946
贪心算法：我们先将问题的区间集合按右端点排序，从最左边的区间开始，如果该区间内雷达为空为空，则选区间最右边的端点放雷达，并删掉左端点在雷达前的区间，进入子问题。
Code from http://www.hankcs.com/program/cpp/poj-1328-radar-installation-challenge-programming-contest-2nd-edition-exercises-answers.html
Also check http://ren.iteye.com/blog/344093
Read full article from 1328 -- Radar Installation
Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.
We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.
Input
The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.
3 2 1 2 -3 1 2 1
贪心算法：我们先将问题的区间集合按右端点排序，从最左边的区间开始，如果该区间内雷达为空为空，则选区间最右边的端点放雷达，并删掉左端点在雷达前的区间，进入子问题。
下面来证明算法的正确性：
即要证两点：
（1）贪心选择性
（2）最优子结构性质
首先我们先来想想最原始的做法。就是在一堆区间中选几个点。那么我们可以拆分成若干步，每一步选一个点。选过之后，包含该点的区间都被覆盖，这样原问题划分为两个子问题，并显然满足最优子结构性质。假如雷达的坐标限定为整数，那么我们就可以采用动态规划的方法来解题。但雷达的坐标是实数，所以我们只有另辟蹊径。
经验，应该来说是通过经验，我们想到了上文所说得贪心算法。至于为什么这么做，只能说贪心算法的模式一般都是在极端处取值（可以参照活动选择问题的解法)。如果我们知道了该选择是贪心选择，即最优解的一种包含该选择，那么我们再根据上文叙述的最优子结构性质即可证明算法的正确性。（即求得的解不会比包含贪心选择的最优解大，否则与最优子问题矛盾）
下面我们证明该选择是贪心选择。
首先我们证明，子问题的第一个区间必定只能包含一个点。因为在求解子问题之前定下的点不会落在该区间，否则该区间就不会出现在子问题中；并且在求解该子问题时，该区间也不会落入两个点，否则我们去掉左边那个点，对问题没有影响（本质是因为按尾部递增排列）。请看图示：
..
----
----
----
每一个点“照看”一簇区间，左边那个点能照看到的区间，右边那个点都能照看到。因此在最优解中，第一个区间有且只有一个点。然而其他的区间则不一定，因为在子问题中新增的点可能落在之前被删掉的区间内。
首先我们证明，子问题的第一个区间必定只能包含一个点。因为在求解子问题之前定下的点不会落在该区间，否则该区间就不会出现在子问题中；并且在求解该子问题时，该区间也不会落入两个点，否则我们去掉左边那个点，对问题没有影响（本质是因为按尾部递增排列）。请看图示：
..
----
----
----
每一个点“照看”一簇区间，左边那个点能照看到的区间，右边那个点都能照看到。因此在最优解中，第一个区间有且只有一个点。然而其他的区间则不一定，因为在子问题中新增的点可能落在之前被删掉的区间内。
这点明确之后，我们就可以开始我们的证明。因为第一个区间有且只有一点，那么假设在最优解中这一点不是放在最右端点，那么我们可以把这一点移到最右端点，并不影响它覆盖的islands。原因就不必赘述了。这样我们就得到了另一个最优解。因此，选第一个区间的最右端点是安全的选择，亦即贪心选择。
这样我们就比较完整的证明了算法的正确性了。
Code from http://www.hankcs.com/program/cpp/poj-1328-radar-installation-challenge-programming-contest-2nd-edition-exercises-answers.html
贪心策略依然是从左往右，尽量让每颗雷达覆盖最大岛屿数。
对整个题目数据的处理有个思维转换的过程，如果从雷达这个点出发去思考，那么会陷入double无尽的遍历中去。
我的思路是，先对每个海岛求一个区间：能覆盖它的所有雷达的圆心所构成的区间。然后对区间排序，定义一个最右点end，依次延伸end，如果end不在某个区间内，那么消耗一颗雷达，end更新为该区间的最右端，否则end更新为起点在end内的所有区间的最小右端点。
struct Section{ double begin; double end; bool operator < (const Section& b) const { return begin < b.begin; } };int main(int argc, char *argv[]){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif int n, d, __id; __id = 0; while(cin >> n >> d && n > 0) { int result = 0; vector<Section> s(n); for (int i = 0; i < n; ++i) { double x, y; cin >> x >> y; if (result == -1) { continue; } if (y > d) { // 如果y比半径大，一定不能覆盖 result = -1; continue; } double r = sqrt(d * d - y * y); s[i].begin = x - r; s[i].end = x + r; } if (result == -1) { cout << "Case " << ++__id << ": " << result << endl; continue; } sort(s.begin(), s.end()); double end = -numeric_limits<double>::max(); for (vector<Section>::iterator it = s.begin(); it != s.end(); ++it) { // cout << it->begin << " " << it->end << endl; if (end < it->begin) { ++result; end = it->end; } else if (end > it->end) { end = it->end; } } cout << "Case " << ++__id << ": " << result << endl; }#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}Also check http://ren.iteye.com/blog/344093
Read full article from 1328 -- Radar Installation
