fac2_10.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 48 页，例
//最接近点对问题的分治解法
 
   public  class Fac2_10
 {
 static class Point 
  {
    double x,y;     //点坐标
        public Point(double xx,double yy)
         {
           x=xx;
           y=yy;
         }
  }
   
   static class Point1 extends Point 
    {
      int id;   //点编号
        public Point1(double xx,double yy,int theID)
      {
       super(xx,yy);
       id=theID;
      }
 
    public boolean equals(Object x)
       { return this.x==((Point1) x).x;}
   }       
 
    static class Point2 extends Point 
    {
       int p;   //同一点在数组X中的坐标
       public  Point2(double xx,double yy,int pp)
      {

       super(xx,yy);
       p=pp;
      }
  
    public boolean equals(Object x)
       { return this.y==((Point1) x).y;}
   }
   
   static class Pair
       {
        Point1 a;   //平面点a
        Point1 b;   // 平面点b 
        double dist;  //平面点a和b间的距离
       public Pair(Point1 aa,Point1 bb,double dd)
         {
           a=aa;
           b=bb;
           dist=dd;
         } 
       }
   public static double distance(Point u,Point v)
      {
        double dx=u.x-v.x;
        double dy=u.y-v.y;
        return  Math.sqrt(dx*dx+dy*dy);
      }
 
   public static void mergeSort(Point1 []a)
    {
     Point1 []b=new Point1[a.length];
     int s=1;
     while(s<a.length){
        mergePass(a,b,s);
        s+=s;
        mergePass(b,a,s);
        s+=s;
        }
     }
   public static void mergePass(Point1[] x,Point1[] y,int s)
     { 
      int i=0;
      while(i<=x.length-2*s)
      {
      merge(x,y,i,i+s-1,i+2*s-1);
      i=i+2*s;
      }
      if(i+s<x.length)
      merge(x,y,i,i+s-1,x.length-1);
      else
      for(int j=i;j<x.length;j++)
       y[j]=x[j];
     }
  public static void merge(Point1[] c,Point1[] d,int l,int m,int r)
     {
      int i=l,
          j=m+1,
          k=l;
      while((i<=m)&&(j<=r))
          if(c[i].x-c[j].x<=0)
             d[k++]=c[i++];
          else d[k++]=c[j++];
          if(i>m)
          for(int q=j;q<=r;q++)
              d[k++]=c[q];
          else 
           for(int q=i;q<=m;q++)
              d[k++]=c[q];
      }
//*********************************************************
  public static void mergeSort(Point2 []a)
    {
     Point2 []b=new Point2[a.length];
     int s=1;
     while(s<a.length){
        mergePass(a,b,s);
        s+=s;
        mergePass(b,a,s);
        s+=s;
        }
     }
   public static void mergePass(Point2[] x,Point2[] y,int s)
     { 
      int i=0;
      while(i<=x.length-2*s)
      {
      merge(x,y,i,i+s-1,i+2*s-1);
      i=i+2*s;
      }
      if(i+s<x.length)
      merge(x,y,i,i+s-1,x.length-1);
      else
      for(int j=i;j<x.length;j++)
       y[j]=x[j];
     }
  public static void merge(Point2[] c,Point2[] d,int l,int m,int r)
     {
      int i=l,
          j=m+1,
          k=l;
      while((i<=m)&&(j<=r))
          if(c[i].y-c[j].y<=0)
             d[k++]=c[i++];
          else d[k++]=c[j++];
      if(i>m)
          for(int q=j;q<=r;q++)
              d[k++]=c[q];
      else 
          for(int q=i;q<=m;q++)
              d[k++]=c[q];
    }
     
       
  public static Pair cpair2(Point1 []x)
    {
      if(x.length<2)return null;
     // 依X坐标排序
      mergeSort(x);
      Point2 [] y=new Point2[x.length];
      for(int i=0;i<x.length;i++)
      // 将数组X中的点复制到数组Y中
        y[i]=new Point2(x[i].x,x[i].y,i);
        mergeSort(y);//依Y坐标排序
        Point2 []z=new Point2[x.length];
      // 计算最近点对
      return closestPair(x,y,z,0,x.length-1);
    }
  private static Pair closestPair(Point1 []x,Point2 []y,Point2 []z,int l,int r)
    {
      if(r-l==1)  //2点的情形       
         return new Pair(x[l],x[r],distance(x[l],x[r]));
      if(r-l==2)
      { //3点的情形
         double d1=distance(x[l],x[l+1]);
         double d2=distance(x[l+1],x[r]);
         double d3=distance(x[l],x[r]);
      //  System.out.println("d1="+d1+" d2="+d2+" d3= "+d3); 
         if(d1<=d2 && d1<=d3)
            return  new Pair(x[l],x[l+1],d1);
         if(d2<=d3)
             return  new Pair(x[l+1],x[r],d2);
            else 
              return  new Pair(x[l],x[r],d3);
     }
     //多于3点的情形，用分治法
      int m=(l+r)/2;
      int f=l,
          g=m+1;
      for(int i=l;i<=r;i++)
        if(y[i].p>m)z[g++]=y[i];
         else
            z[f++]=y[i];
     //递归求解
      Pair best=closestPair(x,z,y,l,m);
      Pair right=closestPair(x,z,y,m+1,r);
       if(right.dist<best.dist)best=right;
       merge(z,y,l,m,r); //重构数组Y
      //d矩形条内的点置于Z中
      int k=l;
      for(int i=l;i<=r;i++)
       if(Math.abs(x[m].x-y[i].x)<best.dist)
         z[k++]=y[i];
       //搜索Z[l:k-1]
      for(int i=l;i<k;i++)
       {
        for(int j=i+1;j<k && z[j].y-z[i].y<best.dist;j++)
         {
           double dp=distance(z[i],z[j]);
           if(dp<best.dist)
             best=new Pair(x[z[i].p],x[z[j].p],dp);
      //     System.out.println(best.a.id+"  "+best.b.id+"  "+best.dist); 
         }
       }
      return best;
   }


      public static void main(String args[])
  {
    Point1 v[]=new Point1[5];
    v[0]=new Point1(1.0d,1.0d,1);
    v[1]=new Point1(2.0d,1.0d,2);
    v[2]=new Point1(2.5d,2.5d,3);
    v[3]=new Point1(3.0d,3.0d,4);
    v[4]=new Point1(4.0d,4.0d,5);  
    System.out.println("接近最点号  "+cpair2(v).a.id+"   最接近点号  "+
                cpair2(v).b.id+"   距离   "+cpair2(v).dist); 
  }
}