import java.awt.Graphics;
import java.applet.Applet;
import java.awt.Color;
public class hiltsp extends java.applet.Applet{
    Color col1,col2,col3;
    double piaw=3.14159265358979;
    int Naw;
    int takaaw,habaaw;
    int kaw,iaw,jaw;
    int gintQNum;
    int gintQ[]=new int[100];
    String NS,habaS,takaS;
    double Nd,takad,habad;
    double x1aw[]=new double[100];
    double y1aw[]=new double[100];
    double w1aw[]=new double[100];
    int xaw[]=new int[100];
    int yaw[]=new int[100];
    int waw[]=new int[100];
    double saw[]=new double[100];
    String sssaw[]=new String[100];

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

    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.white;
        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];
        for(j=1;j<=gintQNum;j++){
            gintQ[j]=inti[j];
        }//j
    }


    public void paint(java.awt.Graphics g){
        int inti1,inti2,inti3,inti4,inti5,inti6,inti7,inti8,inti9,inti10;
        int N;
        int intdummyi1,j,k,intOrder;
        int intlabel[]=new int[100];
        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;
        g.setColor(col1);
        habaaw=500;
        takaaw=350;
        g.fillRect(1,1,habaaw,takaaw);

        g.setColor(col3);

        g.drawString("Please wait...",1,takaaw);

        N=(int)(Math.random()*46+4);
        for(k=0;k<N;k++){
            dblx[k]=Math.random()*300+100;
            dbly[k]=Math.random()*300+25;
            dbld[k]=9999.9;
            dblw[k]=9999.9;
            g.fillOval((int)dblx[k]-2,(int)dbly[k]-2,4,4);
        }

        g.setColor(col2);
        dblOldx=0.0;
        dblOldy=0.0;
        intOrder=7;//(int)(randaw()*7)+1;
        for(inti1=0;inti1<=3;inti1++){
            if(intOrder==1){
                gintQNum=1;
                inti[1]=inti1;
                sDecOrder(inti);
                dblNewx=fdblCalcx();
                dblNewy=fdblCalcy();
                g.drawLine((int)dblOldx*1+100,325-(int)dblOldy*1,(int)dblNewx*1+100,325-(int)dblNewy*1);
                dblOldx=dblNewx;
                dblOldy=dblNewy;
            }
            else{
                for(inti2=0;inti2<=3;inti2++){
                    if(intOrder==2){
                        gintQNum=2;
                        inti[1]=inti1;
                        inti[2]=inti2;
                        sDecOrder(inti);
                        dblNewx=fdblCalcx();
                        dblNewy=fdblCalcy();
                        g.drawLine((int)dblOldx*1+100,325-(int)dblOldy*1,(int)dblNewx*1+100,325-(int)dblNewy*1);
                        dblOldx=dblNewx;
                        dblOldy=dblNewy;
                    }
                    else{
                        for(inti3=0;inti3<=3;inti3++){
                            if(intOrder==3){
                                gintQNum=3;
                                inti[1]=inti1;
                                inti[2]=inti2;
                                inti[3]=inti3;
                                sDecOrder(inti);
                                dblNewx=fdblCalcx();
                                dblNewy=fdblCalcy();
                                g.drawLine((int)dblOldx*1+100,325-(int)dblOldy*1,(int)dblNewx*1+100,325-(int)dblNewy*1);
                                dblOldx=dblNewx;
                                dblOldy=dblNewy;
                            }
                            else{
                                for(inti4=0;inti4<=3;inti4++){
                                    if(intOrder==4){
                                        gintQNum=4;
                                        inti[1]=inti1;
                                        inti[2]=inti2;
                                        inti[3]=inti3;
                                        inti[4]=inti4;
                                        sDecOrder(inti);
                                        dblNewx=fdblCalcx();
                                        dblNewy=fdblCalcy();
                                        g.drawLine((int)dblOldx*1+100,325-(int)dblOldy*1,(int)dblNewx*1+100,325-(int)dblNewy*1);
                                        dblOldx=dblNewx;
                                        dblOldy=dblNewy;
                                    }
                                    else{
                                        for(inti5=0;inti5<=3;inti5++){
                                            if(intOrder==5){
                                                gintQNum=5;
                                                inti[1]=inti1;
                                                inti[2]=inti2;
                                                inti[3]=inti3;
                                                inti[4]=inti4;
                                                inti[5]=inti5;
                                                sDecOrder(inti);
                                                dblNewx=fdblCalcx();
                                                dblNewy=fdblCalcy();
                                                g.drawLine((int)dblOldx*1+100,325-(int)dblOldy*1,(int)dblNewx*1+100,325-(int)dblNewy*1);
                                                dblOldx=dblNewx;
                                                dblOldy=dblNewy;
                                            }
                                            else{
                                                for(inti6=0;inti6<=3;inti6++){
                                                    if(intOrder==6){
                                                        gintQNum=6;
                                                        inti[1]=inti1;
                                                        inti[2]=inti2;
                                                        inti[3]=inti3;
                                                        inti[4]=inti4;
                                                        inti[5]=inti5;
                                                        inti[6]=inti6;
                                                        sDecOrder(inti);
                                                        dblNewx=fdblCalcx();
                                                        dblNewy=fdblCalcy();
                                                        g.drawLine((int)dblOldx*1+100,325-(int)dblOldy*1,(int)dblNewx*1+100,325-(int)dblNewy*1);
                                                        dblOldx=dblNewx;
                                                        dblOldy=dblNewy;
                                                    }
                                                    else{
                                                        for(inti7=0;inti7<=3;inti7++){
                                                            if(intOrder==7){
                                                                gintQNum=7;
                                                                inti[1]=inti1;
                                                                inti[2]=inti2;
                                                                inti[3]=inti3;
                                                                inti[4]=inti4;
                                                                inti[5]=inti5;
                                                                inti[6]=inti6;
                                                                inti[7]=inti7;
                                                                sDecOrder(inti);
                                                                dblNewx=fdblCalcx();
                                                                dblNewy=fdblCalcy();
                                                                g.drawLine((int)dblOldx*1+100,325-(int)dblOldy*1,(int)dblNewx*1+100,325-(int)dblNewy*1);
                                                                for(j=0;j<N;j++){
                                                                    dd=d(dblx[j],dbly[j],dblNewx+100.0,325.0-dblNewy);
                                                                    if(dd<dbld[j]){
                                                                        dbld[j]=dd;
                                                                        dblw[j]=inti1*4096.0+inti2*1024.0+inti3*256.0+inti4*64.0+inti5*16.0+inti6*4.0+inti7*1.0;
                                                                    }//dd<dbld[j]
                                                                }//j
                                                                dblOldx=dblNewx;
                                                                dblOldy=dblNewy;
                                                            }
                                                            else{
                                                                for(inti8=0;inti8<=3;inti8++){
                                                                    if(intOrder==8){
                                                                        gintQNum=8;
                                                                        inti[1]=inti1;
                                                                        inti[2]=inti2;
                                                                        inti[3]=inti3;
                                                                        inti[4]=inti4;
                                                                        inti[5]=inti5;
                                                                        inti[6]=inti6;
                                                                        inti[7]=inti7;
                                                                        inti[8]=inti8;
                                                                        sDecOrder(inti);
                                                                        dblNewx=fdblCalcx();
                                                                        dblNewy=fdblCalcy();
                                                                        g.drawLine((int)dblOldx*1+100,325-(int)dblOldy*1,(int)dblNewx*1+100,325-(int)dblNewy*1);
                                                                        for(j=0;j<N;j++){
                                                                            dd=d(dblx[j],dbly[j],dblNewx+100.0,325.0-dblNewy);
                                                                            if(dd<dbld[j]){
                                                                                dbld[j]=dd;
                                                                                dblw[j]=inti1*4096.0+inti2*1024.0+inti3*256.0+inti4*64.0+inti5*16.0+inti6*4.0+inti7*1.0+inti8/4.0;
                                                                            }//dd<dbld[j]
                                                                        }//j
                                                                        dblOldx=dblNewx;
                                                                        dblOldy=dblNewy;
                                                                    }
                                                                    else{
                                                                        for(inti9=0;inti9<4;inti9++){
                                                                            if(intOrder==9){
                                                                                gintQNum=9;
                                                                                inti[1]=inti1;
                                                                                inti[2]=inti2;
                                                                                inti[3]=inti3;
                                                                                inti[4]=inti4;
                                                                                inti[5]=inti5;
                                                                                inti[6]=inti6;
                                                                                inti[7]=inti7;
                                                                                inti[8]=inti8;
                                                                                inti[9]=inti9;
                                                                                sDecOrder(inti);
                                                                                dblNewx=fdblCalcx();
                                                                                dblNewy=fdblCalcy();
                                                                                g.drawLine((int)dblOldx*1+100,325-(int)dblOldy*1,(int)dblNewx*1+100,325-(int)dblNewy*1);
                                                                                for(j=0;j<N;j++){
                                                                                    dd=d(dblx[j],dbly[j],dblNewx+100.0,325.0-dblNewy);
                                                                                    if(dd<dbld[j]){
                                                                                        dbld[j]=dd;
                                                                                        dblw[j]=inti1*4096.0+inti2*1024.0+inti3*256.0+inti4*64.0+inti5*16.0+inti6*4.0+inti7*1.0+inti8/4.0+inti9/16.0;
                                                                                    }//dd<dbld[j]
                                                                                }//j
                                                                                dblOldx=dblNewx;
                                                                                dblOldy=dblNewy;
                                                                            }
                                                                            else{
                                                                                for(inti10=0;inti10<4;inti10++){
                                                                                    if(intOrder==10){
                                                                                        gintQNum=10;
                                                                                        inti[1]=inti1;
                                                                                        inti[2]=inti2;
                                                                                        inti[3]=inti3;
                                                                                        inti[4]=inti4;
                                                                                        inti[5]=inti5;
                                                                                        inti[6]=inti6;
                                                                                        inti[7]=inti7;
                                                                                        inti[8]=inti8;
                                                                                        inti[9]=inti9;
                                                                                        inti[10]=inti10;
                                                                                        sDecOrder(inti);
                                                                                        dblNewx=fdblCalcx();
                                                                                        dblNewy=fdblCalcy();
                                                                                        g.drawLine((int)dblOldx*1+100,325-(int)dblOldy*1,(int)dblNewx*1+100,325-(int)dblNewy*1);
                                                                                        for(j=0;j<N;j++){
                                                                                            dd=d(dblx[j],dbly[j],dblNewx+100.0,325.0-dblNewy);
                                                                                            if(dd<dbld[j]){
                                                                                                dbld[j]=dd;
                                                                                                dblw[j]=inti1*4096.0+inti2*1024.0+inti3*256.0+inti4*64.0+inti5*16.0+inti6*4.0+inti7*1.0+inti8/4.0+inti9/16.0+inti10/64.0;
                                                                                            }//dd<dbld[j]
                                                                                        }//j
                                                                                        dblOldx=dblNewx;
                                                                                        dblOldy=dblNewy;
                                                                                    }
                                                                                    else{
                                                                                    }//intOrder==10
                                                                                }//inti10
                                                                            }//intOrder==9
                                                                        }//inti9
                                                                    }//intOrder==8
                                                                }//inti8
                                                            }//intorder==7
                                                        }//inti7
                                                    }//intOrder==6
                                                }//inti6
                                            }//intOrder=5
                                        }//inti5
                                    }//intorder==4
                                }//inti4
                            }//intorder==3
                        }//inti3
                    }//intOrder==2
                }//inti2
            }//intOrder==1
        }//inti1
        heapv(dblw,dblx,dbly,N);
        g.setColor(col3);
        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<N;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[N-1]-4,(int)dbly[N-1]-4,8,8);
        g.drawString("N="+N,10,40);

        g.setColor(col1);
        g.fillRect(1,takaaw-20,80,20);

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