[POJ1328]Radar Installation[贪心]

#include<cstdio>
#include<cmath>
#include<algorithm>
#define in inline
#define re register
#define int long long
#define db double
using namespace std;
in int read()
{
    int s(0),b(0);char ch;
    do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    if(b) return -s;
    return s;
}
int n,r;
struct segment{
    db l,r;
    bool operator<(const segment &t){return l<t.l;}
}a[1001];
signed main()
{
    int cnt=0;
    while(1)
    {
	int f=0;
	++cnt;
	n=read(),r=read();
	if(!n) break;
	for(re int i=1;i<=n;++i)
	{
	    db x,y;
	    scanf("%lf %lf",&x,&y);
	    if(y>(db)r){f=1;}
	    a[i].l=x-sqrt((db)r*(db)r-y*y);
	    a[i].r=x+sqrt((db)r*(db)r-y*y);
	}
	if(f){printf("Case %lld: -1\n",cnt);continue;}
	sort(a+1,a+n+1);
	int ans=0;
	db pos=-1e10;//当前雷达位置
	for(re int i=1;i<=n;++i)
	{
	    if(a[i].l>pos) pos=a[i].r,++ans;
	    else pos=pos<a[i].r?pos:a[i].r;
	}
	printf("Case %lld: %lld\n",cnt,ans);
    }
    return 0;
}