//本程序取自王曉東編著“算法分析與設計”第 179 頁，例
//園排列問題的回溯解法
//
    class Cercles
      {
        static int n;          //待排列圓的個數
        static float min;      //當前最優值
        static float [] x;     //當前圓排列圓心橫坐標
        static float [] r;     //當前圓排列
       

      public static float circlePerm(int nn,float [] rr)
        {
          n=nn;
          min=100000;
          x=new float[n+1];
          r=rr;
          backtrack(1);
          return min;
        }

      private static void backtrack(int t)
        {
          if(t>n)compute();
          else
            {
            for(int j=t;j<=n;j++)
             {//
               swap(r,t,j);
               float centerx=center(t);
               if(centerx+r[t]+r[1]<min)
                 {  x[t]=centerx;
                    backtrack(t+1);
                 }
               swap(x,t,j);
              }
            }
        }
       static void swap(float[] a,int i1,int j1)
        {  
          float temp;   
          temp=a[i1];
          a[i1]=a[j1];
          a[j1]=temp;
        } 
       private  static float center(int t)
         {
           float temp=0;
           for(int j=1;j<t;j++)
            {
              float valuex=(float)(x[j]+ 2.0 * Math.sqrt(r[t]*r[j]));
              if(valuex>temp)temp=valuex;
            }
              return temp;
         }
      private static void compute()
         {
           float low=0;
           float high=0;
           for(int i=1;i<=n;i++)
             {
             if(x[i]-r[i]<low)low=x[i]-r[i];
             if(x[i]+r[i]>high)high=x[i]+r[i];
             }
           if(high-low<min)min=high-low;
         }
            
   }//

   public class Fac5_10{
  
      public static void main(String args[])
  {
     Cercles abc=new Cercles();
     int n1=3;   
     float v1[]={0.0f,1.0f,1.0f,2.0f};         
     System.out.println("園排列問題的最優解   " + abc.circlePerm(n1,v1));
     for(int k=1;k<=n1;k++)
     System.out.print("  "+abc.x[k]);
     System.out.println();
  }
}