原题: http://poj.org/problem?id=1328
//经典区间覆盖问题
#include<iostream>
#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
struct range
{
double x;
double y;
}r[1001];
int cmp(range a,range b)
{
return a.x<b.x;
}
int main()
{
int n,d;
int c=0;
scanf("%d %d",&n,&d);
while(n!=0||d!=0)
{
c++;
int i;
double x,y;
int count=1;
for(i=0;i<n;i++)
{
scanf("%lf %lf",&x,&y);
if(y>d){
count=-1;
}
r[i].x=x-sqrt(d*d-y*y);
r[i].y=x+sqrt(d*d-y*y);
}
sort(r,r+n,cmp);
if(count!=-1){
double s=r[0].y;
for(i=1;i<n;i++)
{
if(r[i].x>s)
{
count++;
s=r[i].y;
}
if(r[i].x<s&&r[i].y<s)
{
s=r[i].y;
}
}
}
printf("Case %d: %d\n",c,count);
scanf("%d %d",&n,&d);
}
} //AC
