aaa.txt

分治法解决最近对问题 画一条垂直线x=c

  #include   <iostream.h>   
  #include   <stdlib.h>   
  #include   <math.h>   
  #include   <time.h>   
  #define   MAX   20   
    
    
  int   p1,p2;   
    
  
  typedef   struct     //建立结构体变量   
  {   
        int   x;   
        int   y;   
  }node;   
 
    
  float   distance(node   t1,   node   t2)//求两点之间的距离   
  {int   r1   ,   r2;   
    r1=t1.x-t2.x;   
    r2=t1.y-t2.y;   
    return   sqrt(r1*r1+r2*r2);   
    }   
    
  float   min_distance(node   a[],   int   start   ,   int   end   ,int   n   )//递归求最小距离   
  {           int   point_num,middle,i,j,count   =   0;   
              int   in,out;  
              int   g=0;   
              double   d1,d2,d3,d,dist,dist1;   
              node   b[MAX];   
                            point_num   =   end   -   start+1;   
                            
                            if(point_num==2)   
                                          {p1=start;p2=end;   
                                          d=distance(a[start],a[end]);   
                                          return   d;   
                                       
                                          }   
                            if(point_num==3)   
                            {d=distance(a[start],a[start+1]);   
                                p1=start;p2=start+1;                             
                                  if(d>distance(a[start],a[start+2]))   
                                  {d=distance(a[start],a[start+2]);   
                                  p1=start;p2=start+2;   
                                  }   
                                  if(d>distance(a[start+1],a[start+2]))   
                                  {d=distance(a[start+1],a[start+2]);   
                                  p1=start+1;p2=start+2;   
                                  }   
                            }   
                            if(point_num>3)   
                                  {                         middle=(start+end)/2;   
                                                          d1   =   min_distance(a,start,   middle,n);   
                                                          d2   =   min_distance(a,middle+1,   end,n);   
                                  if(d1>d2)   
                                                          {d=d2;   
                                                            p1=middle+1;   
                                                            p2   =   end;   
                                                            }   
                                  else   
                                    {d=d1;   
                                    p1=start;   
                                    p2=middle;   
                                                            }   
                                
                              for(i=0;i<n;i++)   
                              if((a[i].x>=a[middle].x   -   d)&&(a[i].x<a[middle].x   +   d))   
                                      {count++;   
                                      b[g].x=a[i].x;   
                                      b[g].y=a[i].y;   
                                    
                                      g++;   
                                      }   
                                      
                                     
                                      d3=d;   
                                for(i=0;i<count;i++)   
                                      for(j=i+1;j<count;j++)   
                                      {   
                                      dist=distance(b[i],b[j]);   
                      
                                      if(dist<d3)   
                                       
                                      d=dist;   
                                      p1=i;   
                                      p2=j;   
                                      }   
                                       
                                      return   d;   
                
              
  }             
  }   
    void   sort(node   a[],int   n)   
    {     
              int   i,j,t;   
              float   a1,a2   ;   
              
              for(i=0;i<n;i++)   
              for(j=0;j<=n-i;j++)   
                    if(a[j].x>a[j+1].x)   
                    {   t=a[j].x;   
                    a[j].x=a[j+1].x;   
                    a[j+1].x=t;   
                    t=a[j].y;   
                    a[j].y=a[j+1].y;   
                    a[j+1].y=t;   
                    }   
    }   
      
  main()   
  {           int   i;   
              float   d;   
              node   a[MAX];   
              //srand(   (unsigned)time(   NULL   )   );   
              for(i=0;i<MAX;i++)   
              {   
                a[i].x   =   rand()*100/RAND_MAX;     
                a[i].y   =   rand()*100/RAND_MAX;             
                }   
                
              sort(a   ,   MAX);   
              for(i=0;i<MAX;i++)   
                cout<<"<"<<a[i].x<<","<<a[i].y<<">";   
                d   =   min_distance(a,0,MAX   -   1,MAX   );   
                cout<<"**********************************************"<<endl;   
                cout<<"the   nearest   two   points'distance   is"<<d<<endl;   
                cout<<"**********************************************"<<endl;   
                cout<<"the   points   is"<<"<"<<a[p1].x<<","<<a[p1].y<<">"<<"<"<<a[p2].x<<","<<a[p2].y<<">"<<endl;   
                system("pause");   
        
          
  }