学步园

题目链接：

http://poj.org/problem?id=1328

题目意思：

X轴上方有些点，给一个距离d，求在X轴上找最少的点，使得以这些点为圆心以d为半径，能够包围住所有的点。

解题思路：

贪心。

问题等价转换。对于每个X轴上方的点A(x,y),在X轴能扫到它的范围为【x-sqrt(d*d-y*y),x+sqrt(d*d-y*y)】，所以问题就转化为，给定若干区间，求最少的点数，使得每个区间至少有一个点在这些点中。很容易想到，对区间的结尾端点排序，对于每个区间，将点设到结尾端点，这样它能覆盖的区间是最多的。直到后一区间的开始端点超过它时，才不能覆盖。

关键：将题目等价转化，转换成区间形式。这样就好办了。

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 1100
struct Inte
{
    double s,e;
}inte[Maxn];
int n;
double d;

bool cmp(struct Inte a,struct Inte b)
{
    return a.e<b.e; //对后一个端点排序

}
int main()
{
    int ca=0;

    while(scanf("%d%lf",&n,&d)&&n+d)
    {
        bool flag=true;

        for(int i=1;i<=n;i++)
        {
            double x,y,temp;
            scanf("%lf%lf",&x,&y);

            if(y>d)
                flag=false; //肯定不行
            else
            {
                temp=sqrt(d*d-y*y); //求出能覆盖该点的区间
                inte[i].s=x-temp;
                inte[i].e=x+temp;
            }

        }
        printf("Case %d: ",++ca);
        if(!flag)
        {
            printf("-1\n");
            continue;
        }

        sort(inte+1,inte+n+1,cmp);
        int ans=1;
        int cur=1;

        for(int i=2;i<=n;i++)
        {
            if(inte[i].s>inte[cur].e) //该点不能覆盖了
            {
                ans++;
                cur=i;
            }
        }
        printf("%d\n",ans);

    }
   return 0;
}