学步园

区间选点问题，难点再与把题意进行转化

这个题题意是说，海上有n多岛，在海岸线上（x轴）建一个雷达能覆盖到与它距离不超过d的岛，求覆盖所有岛的最小雷达数。

注意到能覆盖每一个岛的范围是一定的。即坐标为x,y的岛只能由[x-sqrt(d*d-y*y),x+sqrt(d*d-y*y)]的雷达覆盖。

所以这个题转化成了，对于所有的区间，求最小的点数能使每个区间都至少有一个点，即区间选点问题

对于区间选点问题，白书上写的很详细......

不过我WA了很多次，原因竟然是少写了一个等号！！！囧.......，看别人的代码是按照 左边排序，不过那样就分很多情况，不推荐.....

code

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <limits>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <string.h>
#include <iostream>
#include <algorithm>
#define Si set<int>
#define LL long long
#define pb push_back
#define PS printf(" ")
#define Vi vector<int>
#define LN printf("\n")
#define lson l,m,rt << 1
#define rson m+1,r,rt<<1|1
#define SD(a) scanf("%d",&a)
#define PD(a) printf("%d\n",a)
#define SET(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i(0);i<(a);i++)
#define FD(i,a) for(int i(a);i>=(1);i--)
#define FOR(i,a,b) for(int i(a);i<=(b);i++)
#define FOD(i,a,b) for(int i(a);i>=(b);i--)
#define readf freopen("input.txt","r",stdin)
#define writef freopen("output.txt","w",stdout)
const int maxn = 1006;
const int INF = ~0U>>1;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const double pi = acos(-1.0);
using namespace std;
int N,D;
struct point{
    double x,y;
}p[maxn];
bool cmp(const point a,const point b){
    if(a.y==b.y) return a.x>b.x;
    return a.y<b.y;
}
void solve(){
    sort(p+1,p+N+1,cmp);
    int cnt=1;
//    FOR(i,1,N){
//        printf("%.5lf      %.5lf \n",p[i].x,p[i].y);
//    }
    double temp=p[1].y;
    FOR(i,2,N){
        if(p[i].x>temp){
            cnt++;
            temp=p[i].y;
        }
    }
    printf("%d\n",cnt);
}
int main()
{
//    readf;
//    writef;
    int x,y;
    double t;
    bool flag;
    int cas=1;
    while(~scanf("%d%d",&N,&D) &&( N || D )){
        flag=true;
        FOR(i,1,N){
            scanf("%d%d",&x,&y);
            if(y<=D && flag){
                t=sqrt((double)(D*D-y*y));
                p[i].x=x-t;
                p[i].y=x+t;
            }else{
                flag=false;
            }
        }
        printf("Case %d: ",cas);
        if(!flag){
            puts("-1");
        }else{
            solve();
        }
        cas++;
    }
    return 0;
}