radar.cpp

2002年ACM Asia-BeiJing的比赛题目及原创算法解决方案：Radar Installation

#include <fstream.h>
#include <math.h>

void sort(int ix[],int iy[],int n){
   int temp;
   for(int i=0;i<n;i++){
      for(int j=0;j<n-i-1;j++)
         if(ix[j]>ix[j+1]){
            temp=ix[j];ix[j]=ix[j+1];ix[j+1]=temp;
            temp=iy[j];iy[j]=iy[j+1];iy[j+1]=temp;
         }
   }

}

int main(){
   ifstream fin;
   fin.open("radar.in");

   int n,d;
   int i,j;
   float gx1,gx2;
   float x1,x2;
   int gnum;
   int casenum=1;
   int ix[1000],iy[1000];
   fin>>n>>d;
   while(n!=0&&d!=0){
      for(i=0;i<n;i++)
         fin>>ix[i]>>iy[i];
      for(i=0;i<n;i++) if(d<iy[i]) {gnum=-1;goto END;}
      gnum=1;
      sort(ix,iy,n);
      gx1=ix[0]-sqrt((double)(d*d-iy[0]*iy[0]));
      gx2=ix[0]+sqrt((double)(d*d-iy[0]*iy[0]));
      for(i=1;i<n;i++){
         x1=ix[i]-sqrt((double)(d*d-iy[i]*iy[i]));
         x2=ix[i]+sqrt((double)(d*d-iy[i]*iy[i]));
         if(x1<gx2){
            gx1=x1>gx1?x1:gx1;
            gx2=x2>gx2?gx2:x2;
         }
         else{
            gnum++;
            gx1=x1;
            gx2=x2;
         }
      }
END:  cout<<"Case "<<casenum++<<": "<<gnum<<endl;
      fin>>n>>d;
   }

   fin.close();
   cin>>i;
   return 1;
}