贪心类题目
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 #include<algorithm>
5 #include<math.h>
6 #include<stdlib.h>
7 using namespace std;
8 #define N 10010
9 struct node
10 {
11 double x,y;
12 }a[N];
13 bool cmp(node a,node b)
14 {
15 return a.x<b.x;
16 }
17 int main()
18 {
19 //int i,j,k;
20 int n,i;
21 double d;
22 int cs=0;
23 while(cin>>n>>d,n+d)
24 {
25 int flag=1;
26 int t,k;
27 for(i=0;i<n;i++)
28 {
29 cin>>t>>k;
30 if(k>d) flag=0;
31 if(flag) {a[i].x=t-sqrt(d*d-k*k);a[i].y=t+sqrt(d*d-k*k);}
32 }
33 cout<<"Case "<<++cs<<": ";
34 if(d<=0||!flag) {cout<<"-1\n";continue;}
35 if(n==1){cout<<"1\n";continue;}
36 sort(a,a+n,cmp);
37 double ans=a[0].y;
38 int sum=1;
39 for(i=1;i<n;i++)
40 {
41 if(a[i].x > ans){sum++;ans=a[i].y;}
42 else
43 {
44 if(a[i].y < ans){ans=a[i].y;}
45 }
46 }
47 cout<<sum<<endl;
48 }
49 return 0;
50 }