import java.awt.*;
import java.applet.Applet;
import java.awt.Color;
import java.awt.Font;
public class notspcli extends Applet implements Runnable{
    Thread th;
    Color col1,col2,col3,col4;
    double piaw=3.14159265358979;
    int N,tim,type,ih,ih2,eha;
    int takaaw,habaaw,labelw,label,majicou,recou;
    int majiiru,counter2;
    String NS,habaS,takaS;
    double Nd,takad,habad,mindmind,dd2;

    Point[] p=new Point[1000];
    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;
    }
    public double rog(double aa){
        double rog1;
        rog1=Math.log(aa);
        return rog1;
    }
    public double dou(String dous){
        double dou1;
        dou1 = (Double.valueOf(dous)).doubleValue();
        return dou1;
    }

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

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

    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 double kosaw(double kosainaw){
        double kos1aw;
        kos1aw=Math.cos(kosainaw);
        return kos1aw;
    }

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

    public void hantei(){
        int ish,ieh;
        eha=N;
        if(type>0){
            if(N>0){
                eha=N-1;
            }
        }
        dd2=0.0;
        for(ih=0;ih<eha;ih++){
            ish=ih;
	    ieh=ih+1;
	    if(ih==N-1){
	        ieh=0;
	    }
            dd2=dd2+d(x1[ish],y1[ish],x1[ieh],y1[ieh]);
        }//next i
        if(dd2<mindmind){
            counter2++;
	    for(ih2=0;ih2<N;ih2++){
	        xmin[ih2]=x1[ih2];
	        ymin[ih2]=y1[ih2];
	    }
            mindmind=dd2;
	    repaint();
        }
    }//hantei

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

    public void init(){
        col1=Color.black;
        col2=Color.yellow;
        col3=Color.white;
        col4=Color.blue;
        takaS=getParameter("takap");
        habaS=getParameter("habap");
        NS=getParameter("Np");
        habad=dou(habaS);
        takad=dou(takaS);
        habaaw=(int)habad;
        takaaw=(int)takad;
        N=0;
        Nd=dou(NS);
        type=(int)Nd;
    }//init

    public void koukan(int kie,int kjs){
        double wx,wy;
        wx=x1[kie];
        wy=y1[kie];
        x1[kie]=x1[kjs];
        y1[kie]=y1[kjs];
        x1[kjs]=wx;
        y1[kjs]=wy;
    }//koukan

    public void majiwaruka(){
        int iw,jw,emaji,is,ie,js,je,majimaji;
        emaji=N;
        if(type>0){
            emaji=N-1;
        }
        labelw=0;
        while(labelw==0){
            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){
	                majijs[majicou]=js;
	                majiie[majicou]=ie;
	                majicou++;
	                if(majicou>10){
        	            break;
        	        }
        	    }
       	        }//j
                if(majicou>10){
       	            break;
	        }
            }//i
            if(majicou>0){
	        majimaji=(int)(randaw()*majicou);
	        js=majijs[majimaji];
	        ie=majiie[majimaji];
	        koukan(ie,js);
	    }
            else{
                break;//labelw=1;
            }
        }//wend label==0
    }//majiwaruka

    public void renzoku4ten(){
        int ere,ire;
        int i0,i1,i2,i3,ki1,ki2;
        double smind,sdd;
    if(N>4){
        ere=N;
        if(type>0){
            ere=N-3;
        }
        label=0;
        while(label==0){
            recou=0;
            for(ire=0;ire<ere;ire++){
	        i0=ire;
	        i1=ire+1;
	        i2=ire+2;
	        i3=ire+3;
	        if(ire==N-3){
		    i3=0;
	        }
	        if(ire==N-2){
		    i2=0;
		    i3=1;
	        }
	        if(ire==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){
                    ki1=i1;
                    ki2=i2;
		    koukan(ki1,ki2);
                    recou++;
                    hantei();
		    break;
	        }
            }//i
            if(recou==0){
                label=1;
            }
        }//wend label==0
        majiwaruka();
        hantei();
    }
    }//renzoku4ten

    public void saisyo(){
        double sd1,sd2;
        if(N>3){
            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

    public void saigo(){
        double sd3,sd4;
        if(N>3){
            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

    public void inijunban(){
        int sini,eini,iini,jini,minj;
if(N>3){
        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

    public void nearest(){
        int yi,yj,enear,minj;
        double dd,mind;
if(N>3){
        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

    public void ten1(){
	int it,jt,kt,sten1,eten1;
        double wx,wy;
if(N>3){
        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

    public void ten2(){
	int it,jt,kt,sten2,eten2;
        double wx1,wy1,wx2,wy2;
if(N>4){
        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

    public void ten2b(){
	int it,jt,kt,sten2b,eten2b;
        double wx1,wy1,wx2,wy2;
if(N>4){
        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,si,v,timlabel,ish,ieh;
        counter2++;
        mindmind=9999999.9;
        tim=0;
        for(;;){
            mindmind=0.0;
            for(ih2=0;ih2<eha;ih2++){
                ish=ih2;
	        ieh=ih2+1;
	        if(ih2==N-1){
	            ieh=0;
	        }
                mindmind=mindmind+d(xmin[ish],ymin[ish],xmin[ieh],ymin[ieh]);
            }//next i*/
            if(N>2){
        	tim++;
            }
	    timlabel=0;
	    if(N>20){
		timlabel=1;
	    }
            if(N>9 && N<21){
	        if(tim % 3==0){
		    timlabel=1;
	        }
            }
            if(N<10 && N>3){
	        if(tim % 10==0){
		    timlabel=1;
	        }
	    }
	    if(N==2 || N==3){
	        if(tim % 100==0){
		    timlabel=1;
	        }
	    }
            if(timlabel==1){
                repaint();
            }
            inijunban();
            if(type<1){
                nearest();
            }
            ev=N*4;
            for(v=0;v<ev;v++){
                majiwaruka();
                hantei();
                renzoku4ten();
                if(type==1){
                    saisyo();
                }
                if(type==1 || type==2){
                    saigo();
                }
            }//v
            ten1();
            hantei();
            majiwaruka();
            hantei();
            ten2();
            hantei();
            majiwaruka();
            hantei();
            ten2b();
            hantei();
            majiwaruka();
            hantei();
        }//u
    }//run

    public void update(Graphics g){
        paint(g);
    }

    public void paint(java.awt.Graphics g){
        int edraw,isd,ied,kaw,i;
        edraw=N;
        if(type>0){
            if(N>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){
            if(N>0){
                g.drawRect((int)xmin[N-1]-10,(int)ymin[N-1]-10,20,20);
            }
        }
        g.setColor(col3);
        for(i=0;i<edraw;i++){
	    isd=i;
	    ied=i+1;
	    if(i==N-1){
	        ied=0;
	    }
            g.drawLine((int)xmin[isd],(int)ymin[isd],(int)xmin[ied],(int)ymin[ied]);
        }//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 boolean mouseDown(Event evt, int x, int y) {
        int mid;
        if(N<50){
            tim=0;
            mindmind=99999.9;
            ih=0;
            dd2=0.0;
            ih2=0;
            mindmind=99999.9;
        eha=N;
        if(type>0){
            if(N>0){
                eha=N-1;
            }
        }
            majicou=1;
            recou=1;
            p[N]=new Point(x,y);
            x1[N]=p[N].x+(Math.cos(N*1.1)+N)*0.0001;
            y1[N]=p[N].y+(Math.sin(N*1.1)+N)*0.001;
            N++;
        }
        else{
            N=0;
        }
        counter2=0;
        repaint();
        return true;
    }

    public void stop(){
        if(th!=null){
            th.stop();
            th=null;
        }
    }
}