POJ 1328 Radar Installation(贪心)

Description

x轴上方有N个岛屿，现在要在x轴上安装尽可能少的雷达(覆盖半径为d)来覆盖所有岛屿，求最少雷达数目

Analyze

思维定势，先想到确定最优雷达位置覆盖第一个岛屿，再检测该雷达是否能覆盖其余岛屿，能则测试下一个岛屿，不能则放下一个雷达，后来实现起来麻烦且难做对。

逆向思维：根据岛屿位置推出雷达可放范围

得到一个个区间，问题转化为用最少的点占领所有的区间(保证每个区间上都有个被选中的点)，画图得出贪心选择方案

什么时候需运用逆向思维

问题涉及两个相互依赖的事物，按照定势思维想不清楚，则站在另一个对立的角度想想，大胆猜测。问题在于很多时候我们并不能意识到自己的思维定势

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

struct node
{
    double x, y;
}a[1005];

struct interval
{
    double l, r;
}b[1005];

bool cmp(interval a, interval b)
{
    return a.l < b.l;
}

int main()
{
    int n, cnt = 1;
    double d;
    while(~scanf("%d%lf", &n, &d))
    {
        if(n == 0 && d == 0)
            break;
        bool flag = 1;
        for(int i = 0; i < n; ++i)
        {
            scanf("%lf%lf", &a[i].x, &a[i].y);
            if(a[i].y > d)
                flag = 0;
        }

        if(!flag)
        {
            cout << "Case " << cnt++ << ": ";
            cout << "-1" << '\n';
        }
        else
        {
            for(int i = 0; i < n; ++i)
            {
                double tem = sqrt(d * d - a[i].y * a[i].y);
                b[i].l = a[i].x - tem;
                b[i].r = a[i].x + tem;
            }
            sort(b, b + n, cmp);
            double right = b[0].r;
            int pos = 1, ans = 1;
            while(pos < n)
            {
                while(b[pos].l <= right)
                {
                    right = min(right, b[pos].r);
                    pos++;
                }
                if(pos < n)
                {
                    ans++;
                    right = b[pos].r;
                }
            }
            cout << "Case " << cnt++ << ": ";
            cout << ans << '\n';
        }
    }
    return 0;
}