转换问题中两个对象的关系会有惊喜

懵逼的 题目

poj

扯淡的 题解

看的LYD神仙的书Orz

对于这种问题我们一般会对每个建筑求一个”在这个区间内放监控都能管辖这个建筑的 区间”, 这样就不用担心圆的性状问题等等…

然后我们对每个区间按照左端点排序, 记录一个”最右监控可以最靠右的位置$pos$”

  • 如果$pos < le_i$, 那么说明最右边的监控也不可能管到这个建筑了, 新建一个监控, $pos = ri_i$
  • 否则$pos = \min(pos, ri_i)$因为$le \le pos$ 所以我们只要让$pos \le ri_i$即可, 而我们无论怎么移动也都不会对前面的监控产生影响(因为是按照左端点排的序)

沙茶的 代码

代码倒是肥肠好写…

有一个坑就是发现当前建筑不合法后不能直接break…要把现在的这组数据读完…

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAXN (100000 + 5)
#define DD double
#define pii pair<DD, DD>
#define eps (0.0000000000001)
using namespace std;
int n, d;
int main()
{
    int Case = 0;
    while (true)
    {
        scanf("%d%d", &n, &d);
        if (!n && !d)
            break;
        pii a[MAXN];
        bool ok = true;
        for (int i = 1, srx, sry; i <= n; i++)
        {
            scanf("%d%d", &srx, &sry);
            if (sry > d)
                ok = false;
            DD srz = sqrt(max((DD)d * d - (DD)sry * sry, 0.0));
            a[i] = make_pair(srx - srz, srx + srz);
        }
        if (!ok)
        {
            printf("Case %d: -1\n", ++Case);
            continue;
        }
        sort(a + 1, a + n + 1);
        DD pos = -100000000000000000;
        int ans = 0;
        for (int i = 1; i <= n; i++)
            if (pos < a[i].first)
                ++ans, pos = a[i].second;
            else
                pos = min(pos, a[i].second);
        printf("Case %d: %d\n", ++Case, ans);
    }
    return 0;
}

By 沙茶 Cansult