4625093_ac_16ms_200k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 83 行

//真理 竟然如此简单......... 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct
{
  double s,e;
}point;
point island[1010];
int n,d,ans;
double me;

int cmp ( const void * a, const void * b)
{
    double ss = (*(point *)a).s -(*(point *)b).s;
  if (ss > 0 ) return 1;
    if (ss < 0 ) return -1;
    if (ss==0)
  {
         double pp=(*(point *)a).e -(*(point *)b).e;
         if (pp > 0) return 1;
         if (pp < 0) return -1;
     }
 }
 
 void solve()
 {
   qsort(island,n,sizeof(island[0]),cmp);
   ans = 1;
   me = island[0].e;
   for(int i=1; i<n; i++)
   {
     if(island[i].s > me)
     {
       me = island[i].e;
       ans++;
     }
     else
     {
       if(island[i].e < me)
       {
         me = island[i].e;
       }
     }
   }
 }
 
 int main()
 {
   int t=1;
   while(scanf("%d%d",&n,&d),(n!=0)||(d!=0))
   {
     bool noans = 0;
     for(int i=0; i<n; i++)
     {
       int x,y;
       scanf("%d%d",&x,&y);
       if(y>d || noans == 1)
       {
         noans = 1;
       }
       else
       {
         double l = sqrt( (double)(d*d - y*y) );
         island[i].s = (double)x-l;
         island[i].e = (double)x+l;
       }
     }
     if(noans==1)
     {
       ans = -1;
       printf("Case %d: %d\n",t++,ans);
     }
     else
     {
       solve();
       printf("Case %d: %d\n",t++,ans);
     }
   }
   return 0;
 }