4625038_ce.cpp

部分PKU上的源码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct
{ 
 double l, r;
}in; // 区间
int cmp( const void *a ,const void *b)
{ 
 return (*(in *)a).l >= (*(in *)b).l ? 1 : -1;
}   //按照左端点排序
int main()
{ 
 int n, d, i, x, y, sw, re, count = 1;
 double pre; 
 in p[1000]; 
 while(1)
 { 
  scanf("%d %d", &n, &d); 
  if(n == 0 && d == 0) break; 
  sw = 1; 
  for(i = 0; i < n; i++)
  {  
   scanf("%d %d", &x, &y); 
   if(d >= y && sw == 1)
   {    
    p[i].l = x - sqrt(d * d - y * y); 
    p[i].r = x + sqrt(d * d - y * y);
   }  
   else  
    sw = 0;  
  } 
  if(sw == 0)
  {  
   printf("Case %d: -1\n", count++); 
   continue; 
  } 
  qsort(p, n, sizeof(in), cmp); //以下为贪心，从左至右 
  re = 1; 
  pre = p[0].r; 
  for(i = 1; i < n; i++)
  {  
   if(p[i].l > pre)
   {   
    re++;   
    pre = p[i].r;
   }  
   else{  
    if(p[i].r < pre) 
     pre = p[i].r; 
  } 
 }  
  printf("Case %d: %d\n", count++, re);
 } 
 return 0;
}