POJ 1328

==>原题链接

不说了，先看看我的提交记录和提交时间。

题目概述

给定一些小岛，在x轴之上，你要在x轴建雷达站，雷达站覆盖半径给定，问最少的雷达站数。

思路

试过别的思路，都会有一些问题。
正确的思路应该是：

网上这个图还不错。
先取每个岛为圆心画圆，交x轴一点或两点，则每个点对的闭区间可满足该岛被覆盖。如果出现两个岛在x轴形成的区间有交集，那么这个交集就可以满足这两个岛都可被覆盖。那么我们的目的就是找出这样的交集的个数，使radar站最少。

方法就是排序。将处理过的x轴上的区间首先按左端点l从小到大排。这样我们可以按照类似POJ 2376的思路，维护一个右端点，如果下一个区间只是有交集，那他的右端点还是原来的右端点，如果是真子集，则需要更新右端点为真子集的右端点，即

mx = p[i].r;

如果没有交集，则说明上一个雷达站已经hold不住了，就再新建一个，mx更新为新的区间的右端点，同时增加雷达站统计数，即

ans++; mx = p[i].r;

循环一次就可以做完，复杂度O(nlgn)，为排序的复杂度。

小吐槽

因为在读取数据的时候多了 break; 而导致没读完就跳出了，就这个毁了一个晚上加一个上午，必须记录一下，吃一堑长一智。

代码

#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

void init();
void solve();

typedef struct
{
    double l, r;
} DATA;

DATA p[1000 + 10];
bool f;
int ans, n, d;

int main()
{
    int i, tcase = 0;
    int x, y;
    freopen("1328.in", "r", stdin);
    while ((~scanf("%d%d", &n, &d)) && !(n == 0 && d == 0))
    {
        f = true, ans = 0;
        printf("Case %d: ", ++tcase);
        for (i = 0; i < n; i++)
        {
            scanf("%d%d", &x, &y);
            if (y > d)
            {
                f = false;
                //break; <==这就是个原来那个sb的break; 读入都敢break; 果然是 腕儿够大;
            }
            p[i].l = x - sqrt((double)(d * d - y * y));
            p[i].r = x + sqrt((double)(d * d - y * y));
        }

        if (f)
        {
            init();
            solve();
            printf("%d\n", ans);
        }
        else
        {
            printf("-1\n");
        }
    }
    return 0;
}

bool cmp(DATA a, DATA b)
{
    if (fabs(a.l - b.l) < 1e-6)
    {
        return a.r - b.r < 1e-6;
    }
    else
    {
        return a.l < b.l;
    }
}

void init()
{
    sort(p, p + n, cmp);
}

void solve()
{
    int i;
    double mx;

    if (n == 0)
    {
        return;
    }
    mx = p[0].r;
    ans = 1;

    for (i = 1; i < n; i++)
    {
        if (p[i].l - mx < 1e-6)
        {
            if (p[i].r - mx < 1e-6)
            {
                mx = p[i].r;
            }
        }
        else
        {
            ans++;
            mx = p[i].r;
        }
    }
}