Uva 2319

理解：区域覆盖。假设该点在勘测半圆的边缘，求出与该点可在一个半圆的坐标范围l,r,然后，for 一次判断

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

using namespace std;

struct  Point

{

    double l,r;

} p[1005];

int cmp(Point a,Point b)//排序的规则由main函数最后的for

{

    if(a.l!=b.l)//必须由右侧为主要，

       return a.l<b.l;

     return a.r>b.r;

}

int main()

{

    int n,d;

    int ct=1;

    while(cin>>n>>d&&(n+d))

    {

        bool flag=0;

        for(int i=0; i<n; i++)

        {

            int x,y;

            cin>>x>>y;

            if(y>d)

                flag=1;

            else

            {

                p[i].l=x+sqrt(d*d-y*y);

                p[i].r=x-sqrt(d*d-y*y);

            }

        }

        if(flag)

            {cout<<"Case "<<ct++<<": -1"<<endl;

            continue;}

        sort(p,p+n,cmp);

        double temp=p[0].l;

        int ans=1;

        for(int i=1; i<n; i++)

        {

            if(p[i].r<=temp)//temp是最远的 即和最远的可以在一个半圆

                continue;

            else

            {

                ans++;

                temp=p[i].l;

            }

        }

        cout<<"Case "<<ct++<<": "<<ans<<endl;

    }

}