import java.awt.Graphics;
import java.applet.Applet;
import java.awt.Color;
import java.awt.*;
public class tsploopv2cli extends java.applet.Applet{

    double dblMinD;
  int idim[]=new int[100];
  int intmindim[]=new int[100];
  int intk;

  Point[] p = new Point[100];
  Color col1,col2;
  int N,n;
  int taka,haba,taka2,haba2;

  long kaiNum;

  long longKumiNum;

  int k,i,j,l,kaw;
  double di2,di,cp2,cpx,ys,t,th;
  double x0,y0,xx,yy,xa1=0,ya1=0,yy2;
  double di4,di3,cp3,cpx3,ys3,t2,ds,us;
  double y20,y21,sa0,sa1;
  int br,br2,u,k2;
  int xz,xz2,yz,yz2;
  String NS,habaS,takaS;
  double Nd,takad,habad;
  Color cl[]=new Color[13];
  double kx[]=new double[100];
  double ky[]=new double[100];
  double kz[]=new double[100];
  public double jou(double a,double b){
    double jou1;
    jou1=Math.pow(a,b);
    return jou1;
  }


    public int majiwaru(double mx1,double my1,double mx2,double my2,double mx3,double my3,double mx4,double my4){
        double mxi,mmeta,mDelta,mlambda,mmu,majieps;
        int majiwaruint;
        mxi=(my4-my3)*(mx4-mx1)-(mx4-mx3)*(my4-my1);
        mmeta=-(my2-my1)*(mx4-mx1)+(mx2-mx1)*(my4-my1);
        mDelta=(mx2-mx1)*(my4-my3)-(my2-my1)*(mx4-mx3);
        mlambda=mxi/mDelta;
        mmu=mmeta/mDelta;
        majieps=0.0;//000001;
        if(mlambda>majieps && mlambda<1.0-majieps && mmu>majieps && mmu<1.0-majieps){
            majiwaruint=1;
        }
        else{
            majiwaruint=0;
        }
        return majiwaruint;
    }//majiwaru


    public int majiwaruka_tsploop(int je){
        int intReturnVal;
        int iw,labelw,iend;

        int is,ie,js;

        intReturnVal=0;

        js=je-1;
        iend=je-3;

        for(iw=iend;iw>0;iw--){
	    ie=iw;
            is=iw-1;
            if(majiwaru(x1[idim[is]],y1[idim[is]],x1[idim[ie]],y1[idim[ie]],x1[idim[js]],y1[idim[js]],x1[idim[je]],y1[idim[je]])==1){
	        intReturnVal=1;
      	        break;
            }
        }//i

        return intReturnVal;

    }//majiwaruka_tsploop



  double dis_k(int i1,int i2){
      double d;
      d=jou(jou(x1[i1]-x1[i2],2.0)+jou(y1[i1]-y1[i2],2.0),0.5);
      return d;
  }//dis_k

  long kaijo(int n){
      long kai;
      int i;
      kai=1;
      for(i=2;i<n;i++){
          kai=kai*i;
      }
      kai=kai/2;
      return kai;
  }//dis_k


  public double dou(String dous){
    double dou1;
    dou1 = (Double.valueOf(dous)).doubleValue();
    return dou1;
  }
  public double rand(){
    double rand1;
    rand1=Math.random();
    return rand1;
  }
  public void init(){
    col1=Color.black;
    col2=Color.yellow;
    cl[0]=new Color(10,199,11);
    cl[1]=Color.green;
    cl[2]=new Color(199,111,238);
    cl[3]=new Color(199,199,0);
    cl[4]=Color.white;
    takaS=getParameter("takap");
    habaS=getParameter("habap");
    NS=getParameter("Np");
    habad=dou(habaS);
    takad=dou(takaS);
    Nd=dou(NS);
    if(Nd==20){
      Nd=3+47*rand();
    }
    haba=(int)habad;
    taka=(int)takad;
    N=(int)Nd;
  }
  double x1[]=new double[100];
  double y1[]=new double[100];
  double w1[]=new double[100];

  double x2[]=new double[100];
  double y2[]=new double[100];
  double w2[]=new double[100];


  int x[]=new int[100];
  int y[]=new int[100];
  double s[]=new double[100];
  String sss[]=new String[100];

  String sKumi[]=new String[1000000];

  void heapv(double te1[],double te2[],double te3[],int NN){
    int kk,kks,ii,jj,mm;
    double b1,b2,b3,c1,c2,c3;
    kks=(int)(NN/2);
    for(kk=kks;kk>=1;kk--){
      ii=kk;
      b1=te1[ii-1];b2=te2[ii-1];b3=te3[ii-1];
      while(2*ii<=NN){
        jj=2*ii;
        if(jj+1<=NN){
          if(te1[jj-1]<te1[jj]){
            jj++;
          }
        }
        if(te1[jj-1]<=b1){
          break;
        }
        te1[ii-1]=te1[jj-1];te2[ii-1]=te2[jj-1];te3[ii-1]=te3[jj-1];
        ii=jj;
      }//wend
      te1[ii-1]=b1;te2[ii-1]=b2;te3[ii-1]=b3;
    }//next kk
    for(mm=NN-1;mm>=1;mm--){
      c1=te1[mm];c2=te2[mm];c3=te3[mm];
      te1[mm]=te1[0];te2[mm]=te2[0];te3[mm]=te3[0];
      ii=1;
      while(2*ii<=mm){
        kk=2*ii;
        if(kk+1<=mm){
          if(te1[kk-1]<=te1[kk]){
            kk++;
          }
        }
        if(te1[kk-1]<=c1){
          break;
        }
        te1[ii-1]=te1[kk-1];te2[ii-1]=te2[kk-1];te3[ii-1]=te3[kk-1];
        ii=kk;
      }//wend
      te1[ii-1]=c1;te2[ii-1]=c2;te3[ii-1]=c3;
    }//next mm

  }//heapv


  void tsploopv2(int con,int idim[]){
        int iindex;
        int intk;
        double dblD;
        int intflag;
        int label;

        label=0;

        iindex=con;

        if(iindex>3){
            if(majiwaruka_tsploop(iindex)==1){
                label=1;
            }
        }

        if(label==0){

        if(iindex<N){



            for(idim[iindex]=1;idim[iindex]<N;idim[iindex]++){
                intflag=0;
                for(intk=0;intk<iindex;intk++){
                    if(idim[intk]==idim[iindex]){
                        intflag=1;
                    }
                }//intk
                if(intflag==0){
                    tsploopv2(iindex+1,idim);
                }
            }//idim[] iindex=1
        }//iindex<N
        else{//iindex==N


            int intsflag;
            String sTmp;
            String sTmp2;


                dblD=0.0;
                for(intk=0;intk<N-1;intk++){
                    dblD=dblD+dis_k(idim[intk],idim[intk+1]);
                }//intk
                dblD=dblD+dis_k(idim[N-1],idim[0]);

                if(dblD<dblMinD){
                    dblMinD=dblD;
                    for(intk=0;intk<N;intk++){
                        intmindim[intk]=idim[intk];
                    }//intk
                }

                longKumiNum++;
        }//iindex==N

        }//label==0


  }//tsploopv2



  public void paint(java.awt.Graphics g){//main
    int intCoN;
    taka=350;
    haba=500;
    taka2=taka;
    haba2=haba;
    taka=taka2*40;
    haba=haba2*40;
    g.setColor(col1);
    g.fillRect(1,1,haba,taka);
    g.setColor(col2);
    Point old,current;
    N=n;
    for(k=0;k<N;k++){
      x1[k]=p[k].x+Math.cos(k*1.1)+k*0.0001;
      y1[k]=p[k].y+Math.sin(k*1.1)+k*0.001;
      x[k]=(int)(x1[k]);
      y[k]=(int)(y1[k]);
      s[k]=jou(x1[k]*x1[k]+y1[k]*y1[k],0.5);
    }

    kaiNum=kaijo(N);

    for(k=0;k<N;k++){
      x2[k]=x1[k];
      y2[k]=y1[k];
      g.fillOval((int)x2[k]-3,(int)y2[k]-3,6,6);
      g.drawString(""+k,(int)x2[k]-3,(int)y2[k]-5);
    }
    for(k=0;k<N;k++){
      x1[k]=x2[k]+haba2*20;
      y1[k]=y2[k]+taka2*20;
    }

    g.drawLine(380,40,480,40);
    g.drawLine(380,35,380,40);
    g.drawLine(480,35,480,40);
    g.drawString("0",380,35);
    g.drawString("100",480,35);




    g.setColor(cl[1]);
    g.drawString("N="+N,15,15);

    g.drawString("Now, TSP computing. Please Wait...",50,15);



    longKumiNum=0;

    dblMinD=99999999999.9;
    int intflag;

   idim[0]=0;
    for(idim[1]=1;idim[1]<N;idim[1]++){
        tsploopv2(2,idim);
    g.setColor(col1);
    g.fillRect(310,1,190,15);

    g.setColor(cl[4]);
    g.drawString(longKumiNum+"/"+kaiNum*2,310,15);
//    g.drawString("Kumi="+longKumiNum+"   "+dblMinD,15,35+longKumiNum*12);
    }//idim[0]

/*
    for(i=0;i<longKumiNum;i++){
        g.drawString("Kumi="+sKumi[i],115,35+i*15);
    }//idim[0]
*/

    g.setColor(cl[4]);
    for(intk=0;intk<N-1;intk++){
        g.drawLine((int)x1[intmindim[intk]]-haba2*20,(int)y1[intmindim[intk]]-taka2*20,(int)x1[intmindim[intk+1]]-haba2*20,(int)y1[intmindim[intk+1]]-taka2*20);
    }
    g.drawLine((int)x1[intmindim[N-1]]-haba2*20,(int)y1[intmindim[N-1]]-taka2*20,(int)x1[intmindim[0]]-haba2*20,(int)y1[intmindim[0]]-taka2*20);


    g.drawString("route_num="+longKumiNum/2,160,30);
    g.drawString("TSP_d="+dblMinD,15,30);


    g.setColor(col1);
    g.fillRect(50,1,260,15);

    g.setColor(cl[4]);
    g.drawString("Completed.",50,15);

  }//main



  public boolean mouseDown(Event evt, int x, int y) {
    if(n<50){
      p[n] = new Point(x,y); n++;
    }
    else{
      n=0;
    }
    repaint();
    return true;
  }

}