UVA 1193 区间相关(greedy)

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstdlib>
 4 #define INF 1e-8
 5 
 6 int n, cas=1;
 7 double x[1010][2], d;
 8 int cmp(const void*a,const void*b)
 9 {
10     double*c=(double*)a,*d=(double*)b;
11     if(c[0]!=d[0]) return c[0]>d[0]?1:0;
12     return c[1]>d[1]?1:0;
13 }
14 int main()
15 {
16     freopen("/home/user/桌面/in","r",stdin);
17     while (scanf("%d%lf", &n, &d) == 2&& n)
18     {
19         int i,work=1,x0,y0;
20         for (i = 0; i < n; i++)
21         {
22             scanf("%d%d", &x0, &y0);
23             if (y0 > d||y0<0)
24             {
25                     work = 0;
26                     for(i++;i<n;i++)
27                         scanf("%*d%*d");
28                     break;
29             }
30             double t = sqrt(d*d - y0 * y0);
31             x[i][0] = x0 - t;
32             x[i][1] = x0 + t;
33         }
34         printf("Case %d: ", cas++);
35         if (!work)
36         {
37             puts("-1");
38             continue;
39         }
40         qsort(x,n,sizeof(x[0]),cmp);
41 //        for(int i=0;i<n;i++) printf("%lf %lf\n",x[i][0],x[i][1]);
42         int j=1;
43         d=x[0][1];
44         for(i=1;i<n;i++)
45         {
46             if(x[i][0]<=d) {if(x[i][1]<d) d=x[i][1];}
47             else
48             {
49                 j++;
50                 d=x[i][1];
51             }
52         }
53         printf("%d\n", j);
54     }
55     return 0;
56 }