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;
    }


    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


    public int majiwaru(double mx1,double my1,double mx2,double my2,double mx3,double my3,double mx4,double my4,java.awt.Graphics ag){
        int majiwaruint;
        majiwaruint=0;
        double slp1;
        double itc1;
        double slp2;
        double itc2;
        double itsx;
        slp1=(my1-my2)/(mx1-mx2);
        itc1=my1-slp1*mx1;
        slp2=(my3-my4)/(mx3-mx4);
        itc2=my3-slp2*mx3;
        itsx=(itc2-itc1)/(slp1-slp2);
        if((itsx-mx3)*(itsx-mx4)<0 && (itsx-mx1)*(itsx-mx2)<0){
            majiwaruint=1;
        }
        return majiwaruint;
    }//majiwaru


    void tsploop(int con,int idim[],java.awt.Graphics ag){
        int iindex;
        int intk;
        double dblD;
        int intflag;

        iindex=con;
        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){
                    int majilabel;
                    majilabel=0;
                    if(iindex>3){
                        for(intk=0;intk<iindex-2;intk++){
                            if(majiwaru(x1[idim[intk]],y1[idim[intk]],x1[idim[intk+1]],y1[idim[intk+1]],x1[idim[iindex-1]],y1[idim[iindex-1]],x1[idim[iindex]],y1[idim[iindex]],ag)==1){
                                majilabel=1;
                                break;
                            }
                        }//intk
                    }
                    if(majilabel==0){
                        tsploop(iindex+1,idim,ag);
                    }
                }
            }//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
    }//tsploop


    void tsploop_bk(int con,int idim[],java.awt.Graphics ag){
        int iindex;
        int intk;
        double dblD;
        int intflag;

        iindex=con;
        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){
                    tsploop(iindex+1,idim,ag);
                }
            }//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
    }//tsploop_bk



    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(cl[1]);
        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);
        }
/*N=8;

x1[0]=100.12;
y1[0]=150.102;
x1[1]=200.3;
y1[1]=200.1;
x1[2]=170.16;
y1[2]=220.11;
x1[3]=175.121;
y1[3]=120.133;
x1[4]=168.5;
y1[4]=160.68;
x1[5]=150.27;
y1[5]=145.65;
x1[6]= 50.45;
y1[6]=190.66;
x1[7]= 55.72;
y1[7]=222.01;
*/

        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];
            y1[k]=y2[k];
        }

        g.drawLine(380,50,480,50);
        g.drawLine(380,45,380,50);
        g.drawLine(480,45,480,50);
        g.drawString("0",380,45);
        g.drawString("100",480,45);

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

        if(N>1){
            g.drawString("Now, TSP computing. Please Wait.",50,15);
        }else{
            g.drawString("Please click in this applet.",50,15);
        }
        longKumiNum=0;

        dblMinD=99999999999.9;
        int intflag;

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

            g.setColor(cl[4]);
            g.drawString(longKumiNum+"/"+kaiNum*2,310,15);
            g.drawString((idim[1]+1)+"/"+N,310,30);
        }//idim[0]

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

        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;
    }

}