题面

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.

Figure A Sample Input of Radar Installations

题意

第一第二象限上有n个点,在x轴上可以选择点作为圆心，作一个半径为d的圆。求最少在x轴上选择多少个点作出的圆能使n个点都被覆盖。若无法达成，则输出-1。

分析（详见蓝书）

对于这n个点，我们可以算出每个点在x轴上的一段能覆盖它的区间l[i]~r[i]。问题转化为:给定N个区间，在x轴上放置最少的点，使每个区间包含至少一个点

然后我们考虑将n个区间按照l[i]从小到大排序，用一个变量pos维护最后一个点的坐标。起初pos为负无穷。

依次考虑每个区间。如果当前区间的l[i]>pos，说明需要再选一个点，pos更新为r[i],计数cnt++。反之，则令pos=min(r[i],pos)。

证明（出处：蓝书）

这个贪心算法可以用“决策包容性”来证明。

首先，对于每个区间l[i]~r[i]，有两种选择:

1.使用已有的监控设备管辖它;

2.新建一台监控设备管辖它；

我们的贪心策略是，当选择1可行时，不会选择2。选择1之后，未来可以在任意位置新建一台监控设备。而选择2则需要在l[i]~r[i]之间新建设备，也就是说，第一项选择未来可能到达的状态包含了第二项选择未来可能到达的状态。

其次，在选择1后，我们把上一台设备调整道min(r[i],pos)的位置，也就是在能管辖i的前提下尽量往后放，“尽量往后放”这个策略未来的可达状态显然也包含了“放在更靠前的位置”未来的可达状态。最后，因为所有区间已经按照l[i]排序，所以这个调整不会影响到已经被管辖的区间，证毕。

CODE

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1005
int n;
double d;
struct node{
    double l,r; 
}q[N];
bool cmp(node x,node y){
    return x.l<y.l;
}
int cnt;
int main(){
    while(scanf("%d%lf",&n,&d)){
        if(!n &&!d) break;
        double pos=-inf;
        int ans=0;
        int flag=1; 
        for(int i=1;i<=n;++i){
            double x,y;
            scanf("%lf%lf",&x,&y);
            q[i].l=x-sqrt(d*d-y*y);
            q[i].r=x+sqrt(d*d-y*y);
            if(y>d) flag=0;
        }
        sort(q+1,q+1+n,cmp);
        for(int i=1;i<=n;++i){
            if(pos<q[i].l){
                ++ans;
                pos=q[i].r;
            }
            else pos=min(q[i].r,pos);
        }
        printf("Case %d: %d\n",++cnt,flag?ans:-1);
    }
    return 0;
}

View Code