POJ 1328 -- Radar Installation

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.

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

http://blog.csdn.net/petercsj/article/details/4602946
贪心算法：我们先将问题的区间集合按右端点排序，从最左边的区间开始，如果该区间内雷达为空为空，则选区间最右边的端点放雷达，并删掉左端点在雷达前的区间，进入子问题。

下面来证明算法的正确性：

即要证两点：

（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