import java.awt.Graphics;
import java.applet.Applet;
import java.awt.Color;
public class itsp extends java.applet.Applet{
    Color col1,col2,col3;
    double piaw=3.14159265358979;
    double dblBasD;
    int Naw;
    int takaaw,habaaw;
    int kaw,iaw,jaw;
    int gintZ[]=new int[100];
    int gintZ2[]=new int[100];
    int gintZMin[]=new int[100];
    String NS,habaS,takaS;
    double Nd,takad,habad;
    double gdblX1[]=new double[10000];
    double gdblY1[]=new double[10000];
    double dblOldSuperX,dblOldSuperY,dblNewSuperX,dblNewSuperY;

    public double dou(String dous){
        double dou1;
        dou1 = (Double.valueOf(dous)).doubleValue();
        return dou1;
    }

    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
    }
    public double d(double d1,double d2,double d3,double d4){
        double dw;
        dw=Math.pow(Math.pow(d3-d1,2.0)+Math.pow(d4-d2,2.0),0.5);
        return dw;
    }
    public void init(){
        col1=Color.black;
        col2=Color.red;
        col3=Color.yellow;
        takaS=getParameter("takap");
        habaS=getParameter("habap");
        NS=getParameter("Np");
        habad=dou(habaS);
        takad=dou(takaS);
        habaaw=(int)habad;
        takaaw=(int)takad;
    }

    public void koukan(int k1, int k2){
        int iw;
        iw = gintZ2[k1];
        gintZ2[k1] = gintZ2[k2];
        gintZ2[k2] = iw;
    }//koukan



    public void paint(java.awt.Graphics g){
        int inti1,inti2,inti3,inti4,inti5,inti6,inti7,inti8,inti9,inti10;
        int intlabel[]=new int[100];
        int N,i,mink,l;
        int intdummyi1,j,k,intOrder;
        double dblx[]=new double[100];
        double dbly[]=new double[100];
        double dbld[]=new double[100];
        double dblw[]=new double[100];
        int inti[]=new int[100];
        double dd;
        double dblOldx,dblOldy,dblNewx,dblNewy,dblsd,dblMinD,dblDD,xx1,xx2,yy1,yy2;
        double mind;
        g.setColor(col1);
        habaaw=500;
        takaaw=350;
        g.fillRect(1,1,habaaw,takaaw);

        g.setColor(col3);
        g.drawString("Please wait...",1,(int)takaaw);
        N=(int)(Math.random()*96.0+4);


        for(k=0;k<N;k++){
            gdblX1[k] = Math.random() * (habaaw - 30) + 15.0;
            gdblY1[k] = Math.random() * (takaaw - 30) + 15.0;
            g.drawOval((int)gdblX1[k]-2,(int)gdblY1[k]-2,4,4);
        }//Next k
        
        gintZMin[0] = 0;
        gintZMin[1] = 1;
        gintZMin[2] = 2;
        for(k=3;k<N;k++){
            gintZMin[k] = k;
            dblMinD = 0.0;
            for(i=0;i<=k;i++){
                gintZ2[i] = gintZMin[i];
                if(i>0){
                    xx1 = gdblX1[gintZMin[i - 1]];
                    yy1 = gdblY1[gintZMin[i - 1]];
                    xx2 = gdblX1[gintZMin[i]];
                    yy2 = gdblY1[gintZMin[i]];
                }else{
                    xx1 = gdblX1[gintZMin[0]];
                    yy1 = gdblY1[gintZMin[0]];
                    xx2 = gdblX1[gintZMin[k]];
                    yy2 = gdblY1[gintZMin[k]];
                }//i > 0
                dblMinD = dblMinD + d(xx1,yy1,xx2,yy2);
            }//next i
            for(i=0;i<k;i++){
                if(i==0){
                    koukan(k, 0);
                }else{
                    koukan(i - 1, i);
                }//i==0



                dblDD = 0.0;
                for( l = 0;l<=k;l++){
                    if(l>0){
                        xx1=gdblX1[gintZ2[l - 1]];
                        yy1 = gdblY1[gintZ2[l - 1]];
                        xx2 = gdblX1[gintZ2[l]];
                        yy2 = gdblY1[gintZ2[l]];
                    }else{
                        xx1 = gdblX1[gintZ2[k]];
                        yy1 = gdblY1[gintZ2[k]];
                        xx2 = gdblX1[gintZ2[0]];
                        yy2 = gdblY1[gintZ2[0]];
                    }//l>0
                    dblDD = dblDD + d(xx1,yy1,xx2,yy2);
                }//Next l
                if(dblDD < dblMinD || k==N){
                    g.setColor(col1);
                    g.fillRect(1,1,habaaw,takaaw);

                    g.setColor(col3);
                    g.drawString("N="+(N),10,40);
                    g.drawString("Please wait...",1,(int)takaaw);
                    for(l=0;l<N;l++){
                        g.drawOval((int)gdblX1[l]-2, (int)gdblY1[l]-2,4,4);
                    }//Next l
                    for(l=0;l<=k;l++){
                        gintZMin[l] = gintZ2[l];
                        if (l > 0){
                            g.drawLine((int)gdblX1[gintZMin[l]], (int)gdblY1[gintZMin[l]],(int)gdblX1[gintZMin[l - 1]], (int)gdblY1[gintZMin[l - 1]]);
                        }//l > 0
                    }//Next l
                    dblMinD = dblDD;
                }//dblDD < dblMinD

                for(l = 0;l<N;l++){
                    g.drawOval((int)gdblX1[l]-2, (int)gdblY1[l]-2,4,4);
                }//Next l
                for( l = 0;l<= k;l++){
                    if( l > 0){
                        g.drawLine((int)gdblX1[gintZMin[l]], (int)gdblY1[gintZMin[l]],(int)gdblX1[gintZMin[l - 1]], (int)gdblY1[gintZMin[l - 1]]);
                        dblsd = d(gdblX1[gintZMin[l]], gdblY1[gintZMin[l]], gdblX1[gintZMin[l - 1]], gdblY1[gintZMin[l - 1]]);
                    }//l > 0
                }//Next l
                g.drawLine((int)gdblX1[gintZMin[k]], (int)gdblY1[gintZMin[k]],(int)gdblX1[gintZMin[0]], (int)gdblY1[gintZMin[0]]);




            }//Next i
        }//next k



        g.drawString("N="+(N),10,40);
        g.setColor(col1);
        g.fillRect(1,(int)takaaw-20,80,20);

        g.setColor(col3);
        g.drawString("Finish!!",1,(int)takaaw);
    }//paint
}//paint(java.awt.Graphics g)