import java.awt.*;
import java.applet.Applet;
import java.awt.Color;
import java.awt.Font;
public class notsp extends Applet implements Runnable{
    Thread th;
    Color col1,col2,col3,col4;
    double piaw=3.14159265358979;
    int N,tim,timlabel,si,yu,type,counter2;
    int takaaw,habaaw,orikaeshi,label,is,ie,js,je,u,v,majimaji,majicou;
    int kaw,iaw,jaw,i,j,minj,i0,i1,i2,i3;
    String NS,habaS,takaS;
    double Nd,takad,habad,xx,yy,lto,xmax,wx,wy,dd,mind,dd2,mindmind,wx1,wx2,wy1,wy2;
    double smind,sdd;
    int majiie[]=new int[100];
    int majijs[]=new int[100];
    double x1[]=new double[100];
    double y1[]=new double[100];
    double x2[]=new double[100];
    double y2[]=new double[100];
    double x3[]=new double[100];
    double y3[]=new double[100];
    double x4[]=new double[100];
    double y4[]=new double[100];
    double x5[]=new double[100];
    double y5[]=new double[100];
    double xmin[]=new double[100];
    double ymin[]=new double[100];

    public void start(){
        if(th==null){
            th=new Thread(this);
            th.start();
        }
    }
    public double randaw(){
        double rand1aw;
        rand1aw=Math.random();
        return rand1aw;
    }

    //log
    public double rog(double aa){
        double rog1;
        rog1=Math.log(aa);
        return rog1;
    }

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

    //power
    public double jouaw(double aaw,double baw){
        double jou1aw;
        jou1aw=Math.pow(aaw,baw);
        return jou1aw;
    }

    //arcsin
    public double arcsinaw(double atasw){
        double artn1saw;
        artn1saw=Math.asin(atasw);
        return artn1saw;
    }

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

    //sin
    public double sainaw(double saiaw){
        double sain1aw;
        sain1aw=Math.sin(saiaw);
        return sain1aw;
    }

    //cos
    public double kosaw(double kosainaw){
        double kos1aw;
        kos1aw=Math.cos(kosainaw);
        return kos1aw;
    }

    //Euclidean distance
    public double d(double d1,double d2,double d3,double d4){
        double dw;
        dw=jouaw(jouaw(d3-d1,2.0)+jouaw(d4-d2,2.0),0.5);
        return dw;
    }

    //check whether two segments cross
    //two segments define ; (mx1,my1)-(mx2,my2)
    //                    ; (mx3,my3)-(mx4,my4)
    //majiwaru=0 if two segments don't cross
    //majiwaru=1 if two segments cross
    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;
    }

    //sort he1,he2,he3 such that
    //he1[0]<he1[1]<...<he1[NNN-1]
    void heap(double he1[],double he2[],double he3[],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=he1[ii-1];b2=he2[ii-1];b3=he3[ii-1];
            while(2*ii<=NN){
                jj=2*ii;
                if(jj+1<=NN){
                    if(he1[jj-1]<he1[jj]){
                        jj++;
                    }
                }
                if(he1[jj-1]<=b1){
                    break;
                }
                he1[ii-1]=he1[jj-1];he2[ii-1]=he2[jj-1];he3[ii-1]=he3[jj-1];
                ii=jj;
            }//wend
            he1[ii-1]=b1;he2[ii-1]=b2;he3[ii-1]=b3;
        }//next kk
        for(mm=NN-1;mm>=1;mm--){
            c1=he1[mm];c2=he2[mm];c3=he3[mm];
            he1[mm]=he1[0];he2[mm]=he2[0];he3[mm]=he3[0];
            ii=1;
            while(2*ii<=mm){
                kk=2*ii;
                if(kk+1<=mm){
                    if(he1[kk-1]<=he1[kk]){
                        kk++;
                    }
                }
                if(he1[kk-1]<=c1){
                    break;
                }
                he1[ii-1]=he1[kk-1];he2[ii-1]=he2[kk-1];he3[ii-1]=he3[kk-1];
                ii=kk;
            }//wend
            he1[ii-1]=c1;he2[ii-1]=c2;he3[ii-1]=c3;
        }//next mm
    }//heap

    //initialize
    public void init(){
        col1=Color.black;
        col2=Color.yellow;
        col3=Color.white;
        col4=Color.pink;
        takaS=getParameter("takap");
        habaS=getParameter("habap");
        NS=getParameter("Np");
        habad=dou(habaS);
        takad=dou(takaS);
        Nd=dou(NS);
        Nd=4-rog(randaw())*21;//4+46*randaw();
        if(Nd>50){
            Nd=50.0;
        }
        habaaw=(int)habad;
        takaaw=(int)takad;
        N=(int)Nd;
        Nd=dou(NS);
        type=(int)Nd;
    }//init


    //change two points
    //(x1[kie],y1[kie])<->(x1[kjs],y1[kjs])
    public void koukan(int kie,int kjs){
        wx=x1[kie];
        wy=y1[kie];
        x1[kie]=x1[kjs];
        y1[kie]=y1[kjs];
        x1[kjs]=wx;
        y1[kjs]=wy;
    }//koukan

    //check any two segments cross each other until two segments don't cross
    public void majiwaruka(){
        int iw,jw,labelw,emaji;
        emaji=N;
        if(type>0){
            emaji=N-1;
        }
        labelw=0;
        while(labelw==0){
       	    labelw=1;
            majicou=0;
	    for(iw=0;iw<emaji-2;iw++){
	        is=iw;
	        ie=iw+1;
	        for(jw=iw+2;jw<emaji;jw++){
	            js=jw;
		    je=jw+1;
		    if(jw==N-1){
		       je=0;
		    }
                    if(majiwaru(x1[is],y1[is],x1[ie],y1[ie],x1[js],y1[js],x1[je],y1[je])==1){
	                labelw=0;
	                majijs[majicou]=js;
	                majiie[majicou]=ie;
	                majicou++;
	                if(majicou>10){
        	            break;
        	        }
        	    }
       	        }//j
                if(labelw==0){
	            if(majicou>10){
        	          break;
        	    }
	        }
            }//i
            if(labelw==0){
	        majimaji=(int)(randaw()*majicou);
	        js=majijs[majimaji];
	        ie=majiie[majimaji];
	        koukan(ie,js);
	    }
        }//wend label==0
    }//majiwaruka

    //check the total distance is minimum
    public void hantei(){
        int ih,eha;
        eha=N;
        if(type>0){
            eha=N-1;
        }
        dd2=0.0;
        for(ih=0;ih<eha;ih++){
            is=ih;
	    ie=ih+1;
	    if(ih==N-1){
	        ie=0;
	    }
            dd2=dd2+d(x1[is],y1[is],x1[ie],y1[ie]);
        }//next i
        if(dd2<mindmind){
            counter2++;
            mindmind=dd2;
	    for(ih=0;ih<N;ih++){
	        xmin[ih]=x1[ih];
	        ymin[ih]=y1[ih];
	    }
	    repaint();
        }
    }//hantei

    //check 4 consecutive points
    //consider 4 consecutive points i,j,k,l
    //if total distance i->j->k->l  is greater than i->k->j->l, change j<->k
    public void renzoku4ten(){
        int ere;
        ere=N;
        if(type>0){
            ere=N-3;
        }
        label=0;
        while(label==0){
 	    label=1;
            for(i=0;i<ere;i++){
	        i0=i;
	        i1=i+1;
	        i2=i+2;
	        i3=i+3;
	        if(i==N-3){
		    i3=0;
	        }
	        if(i==N-2){
		    i2=0;
		    i3=1;
	        }
	        if(i==N-1){
		    i1=0;
		    i2=1;
		    i3=2;
	        }
	        smind=d(x1[i0],y1[i0],x1[i1],y1[i1])+d(x1[i1],y1[i1],x1[i2],y1[i2])+d(x1[i2],y1[i2],x1[i3],y1[i3]);
	        sdd=d(x1[i0],y1[i0],x1[i2],y1[i2])+d(x1[i2],y1[i2],x1[i1],y1[i1])+d(x1[i1],y1[i1],x1[i3],y1[i3]);
	        if(sdd<smind){
	  	    label=0;
		    break;
	        }
            }//i
            if(label==0){
		koukan(i1,i2);
                hantei();
	    }
        }//wend label==0
        majiwaruka();
        hantei();
    }//renzoku4ten

    //check first 3 points
    //if 0->1->2 is greater than 1->0->2, change 0<->1
    public void saisyo(){
        double sd1,sd2;
        sd1=d(x1[0],y1[0],x1[1],y1[1])+d(x1[1],y1[1],x1[2],y1[2]);
	sd2=d(x1[1],y1[1],x1[0],y1[0])+d(x1[0],y1[0],x1[2],y1[2]);
        if(sd2<sd1){
	    koukan(0,1);
            hantei();
            majiwaruka();
            hantei();
	}
    }//saisyo

    //last 3 points
    //if N-3 -> N-2 -> N-1 is greater than N-3 -> N-1 -> N-2, then chage N-2 <-> N-1
    public void saigo(){
        double sd3,sd4;
        sd3=d(x1[N-3],y1[N-3],x1[N-2],y1[N-2])+d(x1[N-2],y1[N-2],x1[N-1],y1[N-1]);
	sd4=d(x1[N-3],y1[N-3],x1[N-1],y1[N-1])+d(x1[N-1],y1[N-1],x1[N-2],y1[N-2]);
        if(sd4<sd3){
	    koukan(N-2,N-1);
            hantei();
            majiwaruka();
            hantei();
	}
    }//saigo

    //decide initial order of points randomly
    public void inijunban(){
        int sini,eini,iini,jini;
        sini=0;
        eini=N;
        if(type>1){
            sini=1;
        }
        if(type==3){
            eini=N-1;
        }
        for(iini=0;iini<eini-sini;iini++){
	    x2[iini]=x1[iini+sini];
	    y2[iini]=y1[iini+sini];
	}
        for(iini=0;iini<eini-sini;iini++){
            minj=(int)(randaw()*(eini-iini-sini));
            x1[iini+sini]=x2[minj];
            y1[iini+sini]=y2[minj];
            for(jini=minj;jini<eini-iini-sini;jini++){
		x2[jini]=x2[jini+1];
		y2[jini]=y2[jini+1];
	    }
        }
    }//inijunban

    //search the nearest point
    public void nearest(){
        int yi,yj,enear;
        enear=N;
        for(yi=0;yi<enear-1;yi++){
            mind=999999.9;
            minj=9999;
            for(yj=yi+1;yj<enear;yj++){
                dd=d(x1[yi],y1[yi],x1[yj],y1[yj]);
                if(dd<mind){
	            mind=dd;
	            minj=yj;
                }//j
       	    }//j
       	    koukan(yi+1,minj);
        }//i
    }//nearest

    //check whether the total distance is less if 1 point is inserted into two points
    public void ten1(){
	int it,jt,kt,sten1,eten1;
        sten1=0;
        eten1=N;
        if(type>1){
            sten1=1;
        }
        if(type==3){
            eten1=N-1;
        }
        for(it=sten1;it<eten1;it++){
	    wx=x1[it];
	    wy=y1[it];
            for(kt=it;kt<eten1-1;kt++){
        	x1[kt]=x1[kt+1];
		y1[kt]=y1[kt+1];
	    }//kt
            for(kt=0;kt<eten1-1;kt++){
         	x4[kt]=x1[kt];
	        y4[kt]=y1[kt];
            }//i
	    for(jt=sten1;jt<eten1-1;jt++){
                for(kt=0;kt<eten1-1;kt++){
         	    x1[kt]=x4[kt];
	            y1[kt]=y4[kt];
                }//i
                for(kt=eten1-1;kt>jt;kt--){
        	    x1[kt]=x1[kt-1];
		    y1[kt]=y1[kt-1];
	        }//k
		x1[jt]=wx;
		y1[jt]=wy;
		hantei();
	    }//j
        }//i
    }//ten1

    //check whether the total distance is less if 2 points it, it+1 is inserted into two points
    public void ten2(){
	int it,jt,kt,sten2,eten2;
        sten2=0;
        eten2=N;
        if(type>1){
            sten2=1;
        }
        if(type==3){
            eten2=N-1;
        }
        for(it=sten2;it<eten2-1;it++){
	    wx1=x1[it];
	    wy1=y1[it];
	    wx2=x1[it+1];
	    wy2=y1[it+1];
            for(kt=it;kt<eten2-2;kt++){
        	x1[kt]=x1[kt+2];
		y1[kt]=y1[kt+2];
	    }//kt
            for(kt=0;kt<eten2-2;kt++){
         	x5[kt]=x1[kt];
	        y5[kt]=y1[kt];
            }//i
	    for(jt=sten2;jt<eten2-2;jt++){
                for(kt=0;kt<eten2-2;kt++){
         	    x1[kt]=x5[kt];
	            y1[kt]=y5[kt];
                }//i
                for(kt=eten2-1;kt>jt+1;kt--){
        	    x1[kt]=x1[kt-2];
		    y1[kt]=y1[kt-2];
	        }//k
		x1[jt]=wx1;
		y1[jt]=wy1;
		x1[jt+1]=wx2;
		y1[jt+1]=wy2;
		hantei();
	    }//j
        }//i
    }//ten2

    //check whether the total distance is less if 2 points it+1, it is inserted into two points
    public void ten2b(){
	int it,jt,kt,sten2b,eten2b;
        sten2b=0;
        eten2b=N;
        if(type>1){
            sten2b=1;
        }
        if(type==3){
            eten2b=N-1;
        }
        for(it=sten2b;it<eten2b-1;it++){
	    wx1=x1[it];
	    wy1=y1[it];
	    wx2=x1[it+1];
	    wy2=y1[it+1];
            for(kt=it;kt<eten2b-2;kt++){
        	x1[kt]=x1[kt+2];
		y1[kt]=y1[kt+2];
	    }//kt
            for(kt=0;kt<eten2b-2;kt++){
         	x5[kt]=x1[kt];
	        y5[kt]=y1[kt];
            }//i
	    for(jt=sten2b;jt<eten2b-2;jt++){
                for(kt=0;kt<eten2b-2;kt++){
         	    x1[kt]=x5[kt];
	            y1[kt]=y5[kt];
                }//i
                for(kt=eten2b-1;kt>jt+1;kt--){
        	    x1[kt]=x1[kt-2];
		    y1[kt]=y1[kt-2];
	        }//k
		x1[jt]=wx2;
		y1[jt]=wy2;
		x1[jt+1]=wx1;;
		y1[jt+1]=wy1;
		hantei();
	    }//j
        }//i
    }//ten2

    public void run(){
        int ev;
        counter2=0;
        for(kaw=0;kaw<N;kaw++){
            x1[kaw]=randaw()*(habaaw-30)+15;
            y1[kaw]=randaw()*(takaaw-30)+15;
            x2[kaw]=x1[kaw];
            y2[kaw]=y1[kaw];
        }
        mindmind=9999999.9;
        tim=0;
        for(;;){
	    tim++;
	    timlabel=0;
	    if(N>20){
		timlabel=1;
	    }
            if(N>9 && N<21){
	        if(tim % 3==0){
		    timlabel=1;
	        }
            }
            if(N<10){
	        if(tim % 10==0){
		    timlabel=1;
	        }
	    }
            if(timlabel==1){
                repaint();
            }
            inijunban();
            if(type<2){
                nearest();
            }
            for(si=0;si<N;si++){
		x3[si]=x1[si];
		y3[si]=y1[si];
	    }
            ev=N*4;
            for(v=0;v<ev;v++){
                for(si=0;si<N;si++){
        	    x1[si]=x3[si];
		    y1[si]=y3[si];
	        }
                majiwaruka();
                hantei();
                renzoku4ten();
                if(type==1){
                    saisyo();
                }
                if(type==1 || type==2){
                    saigo();
                }
            }//v
            for(si=0;si<N;si++){
       	        x1[si]=xmin[si];
		y1[si]=ymin[si];
	    }
            ten1();
            hantei();
            majiwaruka();
            hantei();
            for(si=0;si<N;si++){
       	        x1[si]=xmin[si];
		y1[si]=ymin[si];
	    }
            ten2();
            hantei();
            majiwaruka();
            hantei();
            for(si=0;si<N;si++){
       	        x1[si]=xmin[si];
		y1[si]=ymin[si];
	    }
            ten2b();
            hantei();
            majiwaruka();
            hantei();
        }//u
    }//run

    public void update(Graphics g){
        paint(g);
    }
    public void paint(java.awt.Graphics g){
        int edraw;
        edraw=N;
        if(type>0){
            edraw=N-1;
        }
        g.setColor(col1);
        g.fillRect(1,1,habaaw,takaaw);
        g.setColor(col2);
        g.drawString("N="+N,15,15);
        g.drawString("counter="+tim,15,30);
        for(kaw=0;kaw<N;kaw++){
            g.fillOval((int)x1[kaw]-2,(int)y1[kaw]-2,4,4);
        }
        if(type>1){
            g.drawRect((int)xmin[0]-5,(int)ymin[0]-5,10,10);
        }
        if(type==3){
            g.drawRect((int)xmin[N-1]-5,(int)ymin[N-1]-5,10,10);
        }
        g.setColor(col3);
        for(i=0;i<edraw;i++){
	    is=i;
	    ie=i+1;
	    if(i==N-1){
	        ie=0;
	    }
            g.drawLine((int)xmin[is],(int)ymin[is],(int)xmin[ie],(int)ymin[ie]);
        }//next i
        g.drawString("d="+mindmind,105,15);
        g.drawString("counter2="+counter2,105,30);
        g.drawLine(380,15,480,15);
        g.drawLine(380,15,380,10);
        g.drawLine(430,15,430,10);
        g.drawLine(480,15,480,10);
        g.drawString("0",370,15);
        g.drawString("100",481,15);
    }
    public void stop(){
        if(th!=null){
            th.stop();
            th=null;
        }
    }
}