poj1328

题目大意：给定几个点，求用几个雷达能覆盖全部的点，输入的点为坐标，雷达的半径首先给定！

贪心求解：

#include<stdio.h>  
#include<math.h>  
double x[1005],y[1005]; 
double left[1005],right[1005]; 
double r; 
int n,flag,test; 
int main() 
{ 
    test=1; 
    while(scanf("%d%lf",&n,&r)!=EOF&&(n||r)) 
    { 
     
        int i,j,sum; 
        double  temp;  
        flag=0; 
        sum=1; 
        for(i=0;i<n;i++) 
        { 
            scanf("%lf%lf",&x[i],&y[i]); 
            if(y[i]>r) 
            { 
                flag=1; 
            }        
        } 
        if(flag==1) 
        { 
            printf("Case %d: -1\n",test++); 
            continue; 
        }     
        for(i=0;i<n-1;i++)   
            for(j=0;j<n-i-1;j++)   
                if(x[j]>x[j+1])   
                {   
                    temp=x[j];   
                    x[j]=x[j+1];   
                    x[j+1]=temp;   
                    temp=y[j];   
                    y[j]=y[j+1];   
                    y[j+1]=temp;   
                }     
        for(i=0;i<n;i++) 
        { 
            left[i]=x[i]-sqrt(r*r-y[i]*y[i]); 
            right[i]=x[i]+sqrt(r*r-y[i]*y[i]); 
        }  
        temp=right[0]; 
        for(i=0;i<n-1;i++) 
        { 
            if(left[i+1]>temp) 
            {    
               temp=right[i+1]; 
               sum++; 
            } 
            else  if(right[i+1]<temp) 
            { 
                temp=right[i+1]; 
            } 
        } 
      printf("Case %d: %d\n",test++,sum); 
    } 
    return 0; 
} 

#include<stdio.h>
#include<math.h>
double x[1005],y[1005];
double left[1005],right[1005];
double r;
int n,flag,test;
int main()
{
 test=1;
 while(scanf("%d%lf",&n,&r)!=EOF&&(n||r))
 {
 
  int i,j,sum;
  double  temp;
  flag=0;
  sum=1;
  for(i=0;i<n;i++)
  {
   scanf("%lf%lf",&x[i],&y[i]);
   if(y[i]>r)
   {
       flag=1;
   }    
  }
  if(flag==1)
  {
   printf("Case %d: -1\n",test++);
   continue;
  } 
        for(i=0;i<n-1;i++) 
            for(j=0;j<n-i-1;j++) 
                if(x[j]>x[j+1]) 
                { 
                    temp=x[j]; 
                    x[j]=x[j+1]; 
                    x[j+1]=temp; 
                    temp=y[j]; 
                    y[j]=y[j+1]; 
                    y[j+1]=temp; 
                }   
     for(i=0;i<n;i++)
  {
   left[i]=x[i]-sqrt(r*r-y[i]*y[i]);
   right[i]=x[i]+sqrt(r*r-y[i]*y[i]);
  }
     temp=right[0];
     for(i=0;i<n-1;i++)
     {
      if(left[i+1]>temp)
      { 
      temp=right[i+1];
         sum++;
      }
      else  if(right[i+1]<temp)
      {
       temp=right[i+1];
      }
     }
   printf("Case %d: %d\n",test++,sum);
 }
 return 0;
}

 

补充：软件开发 , C++ ,

上一个：poj并查集
下一个：画矩形