import java.awt.Graphics;
import java.applet.Applet;
import java.awt.Color;
public class hilbtsp extends java.applet.Applet{
    Color col1,col2,col3;
    double piaw=3.14159265358979;
    double dblBasD;
    int Naw;
    int takaaw,habaaw;
    int kaw,iaw,jaw;
    int gintQNum;
    int gintQ[]=new int[100];
    int gintQ2[]=new int[100];
    String NS,habaS,takaS;
    double Nd,takad,habad;
    double dblKoushiX[]=new double[10000];
    double dblKoushiY[]=new double[10000];
    int intKoushiP;
    double dblOldSuperX,dblOldSuperY,dblNewSuperX,dblNewSuperY;

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

    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.yellow;
        col3=Color.blue;
        takaS=getParameter("takap");
        habaS=getParameter("habap");
        NS=getParameter("Np");
        habad=dou(habaS);
        takad=dou(takaS);
        Nd=dou(NS);
        if(Nd==6){
            Nd=4+16*randaw();
        }
        habaaw=(int)habad;
        takaaw=(int)takad;
        Naw=(int)Nd;
    }
    public double jou(double aaw,double baw){
        double jou1aw;
        jou1aw=Math.pow(aaw,baw);
        return jou1aw;
    }

    public double artnaw(double ataw){
        double artn1aw;
        artn1aw=Math.atan(ataw);
        return artn1aw;
    }

    public double sainaw(double saiaw){
        double sain1aw;
        sain1aw=Math.sin(saiaw);
        return sain1aw;
    }
    public int fintE0j(int j){
        int inttempf;
        int i;
        inttempf=0;
        for(i=1;i<=j-1;i++){
            if(gintQ[i]==0){
                inttempf=inttempf+1;
            }
        }//i
        inttempf=(inttempf % 2);
        return inttempf;
    }//fintE0j

    public int fintE3j(int j){
        int inttempf;
        int i;
        inttempf=0;
        for(i=1;i<=j-1;i++){
            if(gintQ[i]==3){
                inttempf=inttempf+1;
            }
        }//i
        inttempf=(inttempf % 2);
        return inttempf;
    }//fintE3j

    public int fintDj(int j){
        int inttempf;
        inttempf=((fintE0j(j)+fintE3j(j)) % 2);
        return inttempf;
    }//fintE3j

    public double fdblCalcx(){
        double dbltempf;
        int j;
        dbltempf=0.0;
        for(j=1;j<=gintQNum;j++){
            if(gintQ[j]!=0){
                dbltempf=dbltempf+(300.0/jou(2.0,j))*jou(-1.0,fintE0j(j))*((1.0-fintDj(j))*gintQ[j]-1.0);
            }//gintQ(j)!=0
        }//j
        return dbltempf;
    }//fCalcx

    public double fdblCalcy(){
        double dbltempf;
        int j;
        dbltempf=0.0;
        for(j=1;j<=gintQNum;j++){
            if(gintQ[j]!=0){
                dbltempf=dbltempf+(300.0/jou(2.0,j))*jou(-1.0,fintE0j(j))*(1.0-fintDj(j)*gintQ[j]);
            }//gintQ(j)!=0
        }//j
        return dbltempf;
    }//fCalcy

    public void sDecOrder(int inti[]){
        int k,j,l;
        int intlabel[]=new int[100];
        intlabel[1]=0;
        intlabel[2]=0;
        intlabel[3]=0;
        intlabel[4]=0;
        intlabel[5]=0;
        intlabel[6]=0;
        intlabel[7]=0;
        for(j=1;j<=gintQNum;j++){
            gintQ[j]=inti[gintQ2[j]];
//            gintQ[j]=inti[j];
        }//j
    }
    public void calckoushi(){
        double mind,dd;
        int mink,j;
        mind=99999.9;
        mink=0;
        for(j=0;j<intKoushiP;j++){
            dd=d(100.0+dblNewSuperX,25.0+dblNewSuperY,dblKoushiX[j],dblKoushiY[j]);
            if(dd<mind){
                mink=j;
                mind=dd;
                if(dd<dblBasD){
                    break;
                }
            }
        }
        dblNewSuperX=dblKoushiX[mink];
        dblNewSuperY=dblKoushiY[mink];
    }


    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,intN;
        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;
        double mind;
        g.setColor(col1);
        habaaw=500;
        takaaw=350;
        g.fillRect(1,1,habaaw,takaaw);

        g.setColor(col2);
        g.drawString("Please wait...",1,301);
        intOrder=6;//(int)(randaw()*6)+2;
        intN=(int)(randaw()*46.0+4);
        N=(int)Math.pow(2,intOrder-1);
        intKoushiP=0;
        for(i=0;i<intN;i++){
            dblx[i]=Math.random()*300.0+100.0;
            dbly[i]=Math.random()*300.0+25.0;
            g.drawOval((int)dblx[i]-2,(int)dbly[i]-2,4,4);
            dbld[i]=9999.9;
            dblw[i]=9999.9;
        }

        g.setColor(col3);
        for(i=0;i<N;i++){
            for(j=0;j<N;j++){
                dblKoushiX[intKoushiP]=100.0+300.0*(i+0.5)/N;
                dblKoushiY[intKoushiP]=325.0-300.0*(j+0.5)/N;
//                g.fillOval((int)dblKoushiX[intKoushiP]-2,(int)dblKoushiY[intKoushiP]-2,4,4);
                intKoushiP=intKoushiP+1;
            }//j
        }//i
        dblBasD=150.1/N;
        intlabel[1]=0;
        intlabel[2]=0;
        intlabel[3]=0;
        intlabel[4]=0;
        intlabel[5]=0;
        intlabel[6]=0;
        intlabel[7]=0;
        for(j=1;j<=intOrder;j++){
             gintQ2[j]=j;
        }//j

        g.setColor(col3);
        dblOldx=0.0;
        dblOldy=0.0;
        dblOldSuperX=0.0;
        dblOldSuperY=0.0;
        for(inti1=0;inti1<=3;inti1++){
            inti[1]=inti1;
            if(intOrder==1){
                gintQNum=1;
                sDecOrder(inti);
                dblNewx=fdblCalcx();
                dblNewy=fdblCalcy();
//                g.setColor(col2);
  //              g.drawLine((int)dblOldx+100,325-(int)dblOldy,(int)dblNewx+100,325-(int)dblNewy);
                dblOldx=dblNewx;
                dblOldy=dblNewy;
            }
            else{
                dblNewSuperX=0.0;
                dblNewSuperY=0.0;
                for(inti2=0;inti2<=3;inti2++){
                    inti[2]=inti2;
                    if(intOrder==2){
                        gintQNum=2;
                        sDecOrder(inti);
                        dblNewx=fdblCalcx();
                        dblNewy=fdblCalcy();
//                        g.setColor(col2);
//                        g.drawLine((int)dblOldx+100,325-(int)dblOldy,(int)dblNewx+100,325-(int)dblNewy);
                        dblNewSuperX=dblNewSuperX+dblNewx/4.0;
                        dblNewSuperY=dblNewSuperY+dblNewy/4.0;
                        dblOldx=dblNewx;
                        dblOldy=dblNewy;
                    }
                    else{
                        dblNewSuperX=0.0;
                        dblNewSuperY=0.0;
                        for(inti3=0;inti3<=3;inti3++){
                            inti[3]=inti3;
                            if(intOrder==3){
                                gintQNum=3;
                                sDecOrder(inti);
                                dblNewx=fdblCalcx();
                                dblNewy=fdblCalcy();
//                                g.setColor(col2);
//                                g.drawLine((int)dblOldx+100,325-(int)dblOldy,(int)dblNewx+100,325-(int)dblNewy);
                                dblNewSuperX=dblNewSuperX+dblNewx/4.0;
                                dblNewSuperY=dblNewSuperY+dblNewy/4.0;
                                dblOldx=dblNewx;
                                dblOldy=dblNewy;
                            }
                            else{
                                dblNewSuperX=0.0;
                                dblNewSuperY=0.0;
                                for(inti4=0;inti4<=3;inti4++){
                                    inti[4]=inti4;
                                    if(intOrder==4){
                                        gintQNum=4;
                                        sDecOrder(inti);
                                        dblNewx=fdblCalcx();
                                        dblNewy=fdblCalcy();
//                                        g.setColor(col2);
//                                        g.drawLine((int)dblOldx+100,325-(int)dblOldy,(int)dblNewx+100,325-(int)dblNewy);
                                        dblNewSuperX=dblNewSuperX+dblNewx/4.0;
                                        dblNewSuperY=dblNewSuperY+dblNewy/4.0;
                                        dblOldx=dblNewx;
                                        dblOldy=dblNewy;
                                    }
                                    else{
                                        dblNewSuperX=0.0;
                                        dblNewSuperY=0.0;
                                        for(inti5=0;inti5<=3;inti5++){
                                            inti[5]=inti5;
                                            if(intOrder==5){
                                                gintQNum=5;
                                                sDecOrder(inti);
                                                dblNewx=fdblCalcx();
                                                dblNewy=fdblCalcy();
//                                                g.setColor(col2);
//                                                g.drawLine((int)dblOldx+100,325-(int)dblOldy,(int)dblNewx+100,325-(int)dblNewy);
                                                dblNewSuperX=dblNewSuperX+dblNewx/4.0;
                                                dblNewSuperY=dblNewSuperY+dblNewy/4.0;
                                                dblOldx=dblNewx;
                                                dblOldy=dblNewy;
                                            }
                                            else{
                                                dblNewSuperX=0.0;
                                                dblNewSuperY=0.0;
                                                for(inti6=0;inti6<=3;inti6++){
                                                    inti[6]=inti6;
                                                    if(intOrder==6){
                                                        gintQNum=6;
                                                        sDecOrder(inti);
                                                        dblNewx=fdblCalcx();
                                                        dblNewy=fdblCalcy();
//                                                        g.setColor(col2);
//                                                        g.drawLine((int)dblOldx+100,325-(int)dblOldy,(int)dblNewx+100,325-(int)dblNewy);
                                                        dblNewSuperX=dblNewSuperX+dblNewx/4.0;
                                                        dblNewSuperY=dblNewSuperY+dblNewy/4.0;
                                                        dblOldx=dblNewx;
                                                        dblOldy=dblNewy;
                                                    }
                                                    else{
                                                        dblNewSuperX=0.0;
                                                        dblNewSuperY=0.0;
                                                        for(inti7=0;inti7<=3;inti7++){
                                                            inti[7]=inti7;
                                                            if(intOrder==7){
                                                                gintQNum=7;
                                                                sDecOrder(inti);
                                                                dblNewx=fdblCalcx();
                                                                dblNewy=fdblCalcy();
//                                                                g.setColor(col2);
//                                                                g.drawLine((int)dblOldx+100,325-(int)dblOldy,(int)dblNewx+100,325-(int)dblNewy);
                                                                dblNewSuperX=dblNewSuperX+dblNewx/4.0;
                                                                dblNewSuperY=dblNewSuperY+dblNewy/4.0;
                                                                dblOldx=dblNewx;
                                                                dblOldy=dblNewy;
                                                            }
                                                            else{
                                                            }//intorder==6
                                                        }//inti7
                                                        if(intOrder==7){
                                                            calckoushi();
                                                            if(dblOldSuperX>1.0){
//                                                                g.setColor(col3);
                                                                g.drawLine((int)dblOldSuperX,350-(int)dblOldSuperY,(int)dblNewSuperX,350-(int)dblNewSuperY);
                                                                for(j=0;j<intN;j++){
                                                                    dd=d(dblx[j],dbly[j],dblNewSuperX,350.0-dblNewSuperY);
                                                                    if(dd<dbld[j]){
                                                                        dbld[j]=dd;
                                                                        dblw[j]=inti1*Math.pow(4.0,5.0)+inti2*Math.pow(4.0,4.0)+inti3*Math.pow(4.0,3.0)+inti4*Math.pow(4.0,2.0)+inti5*Math.pow(4.0,1.0);
                                                                    }
                                                                }//j
                                                            }
                                                            dblOldSuperX=dblNewSuperX;
                                                            dblOldSuperY=dblNewSuperY;
                                                        }//intOrder==7
                                                    }//intorder==6
                                                }//inti6
                                                if(intOrder==6){
                                                    calckoushi();
                                                    if(dblOldSuperX>1.0){
//                                                        g.setColor(col3);
                                                        g.drawLine((int)dblOldSuperX,350-(int)dblOldSuperY,(int)dblNewSuperX,350-(int)dblNewSuperY);
                                                    }
                                                    for(j=0;j<intN;j++){
                                                        dd=d(dblx[j],dbly[j],dblNewSuperX,350.0-dblNewSuperY);
                                                        if(dd<dbld[j]){
                                                            dbld[j]=dd;
                                                            dblw[j]=inti1*Math.pow(4.0,5.0)+inti2*Math.pow(4.0,4.0)+inti3*Math.pow(4.0,3.0)+inti4*Math.pow(4.0,2.0)+inti5*Math.pow(4.0,1.0);
                                                        }
                                                    }//j
                                                    dblOldSuperX=dblNewSuperX;
                                                    dblOldSuperY=dblNewSuperY;
                                                }//intOrder==6
                                            }//intorder==5
                                        }//inti5
                                        if(intOrder==5){
                                            calckoushi();
                                            if(dblOldSuperX>1.0){
//                                                g.setColor(col3);
                                                g.drawLine((int)dblOldSuperX,350-(int)dblOldSuperY,(int)dblNewSuperX,350-(int)dblNewSuperY);
                                            }
                                            dblOldSuperX=dblNewSuperX;
                                            dblOldSuperY=dblNewSuperY;
                                        }//intOrder==5
                                    }//intorder==4
                                }//inti4
                                if(intOrder==4){
                                    calckoushi();
                                    if(dblOldSuperX>1.0){
//                                        g.setColor(col3);
                                        g.drawLine((int)dblOldSuperX,350-(int)dblOldSuperY,(int)dblNewSuperX,350-(int)dblNewSuperY);
                                    }
                                    dblOldSuperX=dblNewSuperX;
                                    dblOldSuperY=dblNewSuperY;
                                }//intOrder==4
                            }//intorder==3
                        }//inti3
                        if(intOrder==3){
                            calckoushi();
                            if(dblOldSuperX>1.0){
//                                g.setColor(col3);
                                g.drawLine((int)dblOldSuperX,350-(int)dblOldSuperY,(int)dblNewSuperX,350-(int)dblNewSuperY);
                            }
                            dblOldSuperX=dblNewSuperX;
                            dblOldSuperY=dblNewSuperY;
                        }//intorder==3
                    }//intOrder==2
                }//inti2
                if(intOrder==2){
                    calckoushi();
                    if(dblOldSuperX>1.0){
//                        g.setColor(col3);
                        g.drawLine((int)dblOldSuperX,350-(int)dblOldSuperY,(int)dblNewSuperX,350-(int)dblNewSuperY);
                    }
                    dblOldSuperX=dblNewSuperX;
                    dblOldSuperY=dblNewSuperY;
                }//intOrder==2
            }//intOrder==1
        }//inti1
        heapv(dblw,dblx,dbly,intN);
        g.setColor(col2);
        g.drawOval((int)dblx[0]-2,(int)dbly[0]-2,4,4);
        g.drawRect((int)dblx[0]-4,(int)dbly[0]-4,8,8);
        for(j=1;j<intN;j++){
            g.drawLine((int)dblx[j-1],(int)dbly[j-1],(int)dblx[j],(int)dbly[j]);
            g.drawOval((int)dblx[j]-2,(int)dbly[j]-2,4,4);
//            g.drawString(""+j,(int)dblx[j],(int)dbly[j]);
        }
        g.drawRect((int)dblx[intN-1]-4,(int)dbly[intN-1]-4,8,8);
        g.setColor(col1);
        g.fillRect(1,281,80,20);

        g.setColor(col2);
        g.drawString("Finish!!",1,301);
        g.drawString("N="+intN,10,40);
    }//paint

    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
    }


}