POJ 1328

 1  
 2 //坐标精度是int
 3 /*
 4 圆心位于 
 5 */
 6 #include <iostream>
 7 #include <cstdlib>
 8 #include <cstring>
 9 #include <cmath>
10 using namespace std; 
11 
12 const int N = 1005;
13 typedef struct Part 
14 {
15     int a, b;
16 };
17 Part q[N];
18 
19 typedef struct Node 
20 {
21     int left, right;
22 };
23 Node node[N];
24 
25 int cmp(const void *a, const void *b)//只能返回int
26 {
27     Part *c = (Part *)a;
28     Part *d = (Part *)b;
29     if(c->b == d->b)
30         return c->a < d->a;
31     return c->b > d->b;
32 }
33 
34 int main()
35 {
36     int i,j,k;
37     int n, d;//d为半径
38     int num = 1;
39     while(cin>>n>>d, n&&d)
40     {
41         /*
42         d<0时输出无解，却忘了发现d<0后，后面还有N行输入要“干”掉.
43         */
44         if(d<=0)
45         {
46             int a, b;
47             for(i=1; i<=n; i++)
48                 cin>>a>>b;
49             cout<<"Case "<<num++<<": "<<-1<<endl;
50             continue;
51         }
52         int cnt = 1;
53         bool flag;
54         for(i=1; i<=n; i++)
55         {
56             cin>>node[i].left>>node[i].right;
57             if(abs(node[i].right)>d)
58             {
59                 flag = true;
60             }
61         }
62         if(flag)
63         {
64             cout<<"Case "<<num++<<": "<<-1<<endl;
65             continue;
66         }
67         
68         for(i=1; i<=n; i++)
69         {//圆心在下面的区间内那么就可以包括那个点 
70             q[i].a = node[i].left - sqrt(1.0*(d*d - node[i].right*node[i].right));
71             q[i].b = node[i].left + sqrt(1.0*(d*d - node[i].right*node[i].right));        
72         }
73         
74         //下面是区间选点问题 
75         qsort(q+1, n, sizeof(Part), cmp);
76         int end = q[1].b;
77         for(i=2; i<=n; i++)
78         {
79             if(end<q[i].a)
80             {
81                 end = q[i].b;
82                 cnt++;
83             }
84         
85         }
86         cout<<"Case "<<num++<<": "<<cnt<<endl; 
87     }
88     return 0; 
89 }
90 
91 
92     
93