import java.awt.*;
import java.applet.Applet;
import java.awt.Color;
import java.awt.Font;

public class msteiner extends Applet implements Runnable{
    Thread th;
    Color col1,col2;
    double pi;
    int tim,timlabel,counter2;
    int N,taka,haba,label,sn,h,er,ni,nj,minj,minNN;
    int k,i,j,l,orikaeshi,co2,sco,NN,koko,coch,coch2;
    double di2,di,cp2,cpx,ys,t,lto,xmax,dd2;
    double tx,ty;
    double x0,y0,xx,yy,xa1=0,ya1=0,yy2,mind;
    double di4,di3,cp3,cpx3,ys3,t2,ds,us;
    double y20,y21,sa0,sa1;
    int br,br2,u,k2,toutta,steinerlabel;
    int xz,xz2,yz,yz2;
    String NS,habaS,takaS;
    double Nd,takad,habad;
    Color cl[]=new Color[13];

    int ncv[]=new int[200];
    int cv[][]=new int[200][200];
    double ei[]=new double[20000];
    double ej[]=new double[20000];
    double ed[]=new double[20000];

    double x1[]=new double[200];
    double y1[]=new double[200];
    double xmin[]=new double[200];
    double ymin[]=new double[200];
    double w1[]=new double[200];
    double x2[]=new double[200];
    double y2[]=new double[200];
    double aa[]=new double[200];
    double bb[]=new double[200];
    double aa2[]=new double[200];
    double bb2[]=new double[200];
    double s[]=new double[200];
    int sl[]=new int[200];
    int sl2[]=new int[200];
    int slmin[]=new int[200];
    int e1[]=new int[200];
    int e2[]=new int[200];
    int e1min[]=new int[200];
    int e2min[]=new int[200];
    int cn[]=new int[2000];
    int cn2[]=new int[200];
    int connect[][]=new int[200][10];
    String sss[]=new String[200];

    public void start(){
        if(th==null){
            th=new Thread(this);
            th.start();
        }
    }

    //compute arc-cos
    public double arccosaw(double atasw){
        double arco;
        arco=Math.acos(atasw);
        return arco;
    }

    //compute arc-sin
    public double arcsinaw(double atasw){
        double artn1saw;
        artn1saw=Math.asin(atasw);
        return artn1saw;
    }

    //compute arc-tan
    public double artnaw(double ataw){
        double artn1aw;
        artn1aw=Math.atan(ataw);
        return artn1aw;
    }

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

    //get random variables
    public double rand(){
        double rand1;
        rand1=Math.random();
        return rand1;
    }
    public void init(){
        col1=Color.black;
        col2=Color.yellow;
        cl[0]=Color.white;
        cl[1]=Color.green;
        cl[2]=Color.cyan;
        takaS=getParameter("takap");
        habaS=getParameter("habap");
        NS=getParameter("Np");
        habad=dou(habaS);
        takad=dou(takaS);
        Nd=dou(NS);
        Nd=4+46*rand();
        haba=(int)habad;//          width of screen
        taka=(int)takad;//          height of screen
        N=(int)Nd;//                number of points(generators)
    }

    //compute power   ^
    public double jou(double a,double b){
        double jou1;
        jou1=Math.pow(a,b);
        return jou1;
    }

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

    //sort such that te1[0]<te1[1]<...<te1[NNh-1]
    void heapv(double te1[],double te2[],double te3[],int NNh){
        int kk,kks,ii,jj,mm;
        double b1,b2,b3,c1,c2,c3;
        kks=(int)(NNh/2);
        for(kk=kks;kk>=1;kk--){
            ii=kk;
            b1=te1[ii-1];b2=te2[ii-1];b3=te3[ii-1];
            while(2*ii<=NNh){
                jj=2*ii;
                if(jj+1<=NNh){
                    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=NNh-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
    }


    //compute convex hull
    public void ch(){
        xmax=x1[N-1];
        orikaeshi=0;
        coch=0;
        coch2=0;
        lto=0.0;

        while(lto!=x2[0]){
            xx=x1[0];
            yy=y1[0];
            for(i=1;i<N;i++){
                w1[i]=arcsinaw((y1[i]-yy)/d(x1[i],y1[i],xx,yy))+pi/2;
                if(x1[i]>xx){
                    w1[i]=3*pi/2-arcsinaw((y1[i]-yy)/d(x1[i],y1[i],xx,yy));
                }
                w1[i]=w1[i]+pi;
                if(w1[i]>2*pi){
                    w1[i]=w1[i]-2*pi;
                }
                if(orikaeshi==1){
                    w1[i]=arcsinaw((y1[i]-yy)/d(x1[i],y1[i],xx,yy))+pi/2;
                    if(x1[i]>xx){
                        w1[i]=3*pi/2-arcsinaw((y1[i]-yy)/d(x1[i],y1[i],xx,yy));
                    }
                    if(w1[i]>2*pi){
                        w1[i]=w1[i]-2*pi;
                    }
                }
            }//next i
            x1[0]=xx;
            y1[0]=yy;
            w1[0]=100.0;
            heapv(w1,x1,y1,N);
            lto=x1[0];
            if(orikaeshi==0){
                aa[coch]=(y1[0]-yy)/(x1[0]-xx);
                bb[coch]=y1[0]-aa[coch]*x1[0];
                coch++;
            }
            else{
                aa2[coch2]=(y1[0]-yy)/(x1[0]-xx);
                bb2[coch2]=y1[0]-aa2[coch2]*x1[0];
                coch2++;
            }
            if(x1[0]==xmax){
                orikaeshi=1;
            }
        }//wend

        for(k=0;k<N;k++){
            x1[k]=x2[k];
            y1[k]=y2[k];
        }
    }//ch

    //compute minimum spanning tree
    void mst(){
        int ik,imst,jmst,co;
        co=0;
        for(imst=0;imst<NN-1;imst++){
            if(sl[imst]<2){
                for(jmst=imst+1;jmst<NN;jmst++){
                    if(sl[jmst]<2){
                        ei[co]=imst+0.0;
                        ej[co]=jmst+0.0;
                        ed[co]=d(x1[imst],y1[imst],x1[jmst],y1[jmst]);
                        co++;
                    }//sl[j]
                }//next j
            }//sl[i]
        }//next i

        heapv(ed,ei,ej,co);
        for(i=0;i<NN;i++){
            ncv[i]=0;
        }
        for(i=0;i<NN;i++){
            cn[i]=0;
        }
        koko=0;
        for(i=0;i<co;i++){
            label=0;
            for(j=0;j<ncv[(int)ei[i]];j++){
                if(cv[(int)ei[i]][j]==(int)ej[i]){
                    label=1;
                }
            }//j
            if(label==0){
                e1[koko]=(int)ei[i];
                e2[koko]=(int)ej[i];
                koko++;
                connect[e1[koko-1]][cn[e1[koko-1]]]=e2[koko-1];
                cn[e1[koko-1]]++;
                connect[e2[koko-1]][cn[e2[koko-1]]]=e1[koko-1];
                cn[e2[koko-1]]++;

                ni=ncv[(int)ei[i]];
                nj=ncv[(int)ej[i]];

                cv[(int)ei[i]][ncv[(int)ei[i]]]=(int)ej[i];
                ncv[(int)ei[i]]++;
                for(j=0;j<nj;j++){
                    cv[(int)ei[i]][ncv[(int)ei[i]]]=cv[(int)ej[i]][j];
                    ncv[(int)ei[i]]++;
                    cv[cv[(int)ej[i]][j]][ncv[cv[(int)ej[i]][j]]]=(int)ei[i];
                    ncv[cv[(int)ej[i]][j]]++;
                    for(k=0;k<ni;k++){
                        cv[cv[(int)ej[i]][j]][ncv[cv[(int)ej[i]][j]]]=cv[(int)ei[i]][k];
                        ncv[cv[(int)ej[i]][j]]++;
                    }
                }//j

                cv[(int)ej[i]][ncv[(int)ej[i]]]=(int)ei[i];
                ncv[(int)ej[i]]++;
                for(j=0;j<ni;j++){
                    cv[(int)ej[i]][ncv[(int)ej[i]]]=cv[(int)ei[i]][j];
                    ncv[(int)ej[i]]++;
                    cv[cv[(int)ei[i]][j]][ncv[cv[(int)ei[i]][j]]]=(int)ej[i];
                    ncv[cv[(int)ei[i]][j]]++;
                    for(k=0;k<nj;k++){
                        cv[cv[(int)ei[i]][j]][ncv[cv[(int)ei[i]][j]]]=cv[(int)ej[i]][k];
                        ncv[cv[(int)ei[i]][j]]++;
                    }
                }//j
            }//label=0
        }//i
    }//mst


    //compute value of the object function, in this case, the length of the total tree
    public double moku(){
        double mokukan;
        int mokuk;
        mokukan=0.0;
        for(mokuk=0;mokuk<NN-1;mokuk++){
            mokukan=mokukan+d(x1[e1[mokuk]],y1[e1[mokuk]],x1[e2[mokuk]],y1[e2[mokuk]]);
        }
        return mokukan;
    }

    //
    void bohe(){
        int hi,hj,hk,hbr,shinNN;
        for(hi=N;hi<NN;hi++){
            x2[hi]=x1[hi];
            y2[hi]=y1[hi];
            sl2[hi]=sl[hi];
            cn[hi]=cn[hi];
        }
        for(hi=N;hi<NN;hi++){
            if(sl[hi]==1 && cn[hi]!=3){
                sl[hi]=2;
            }//sl[i]==1 && cn[i]<3
        }//wend hi
        shinNN=N;
        for(hi=N;hi<NN;hi++){
            if(sl[hi]==1){
                x1[shinNN]=x2[hi];
                y1[shinNN]=y2[hi];
                cn[shinNN]=cn2[hi];
                shinNN++;
            }//sl[hi]==1
        }//hi
        NN=shinNN;
        for(hi=N;hi<NN;hi++){
            sl[hi]=1;
        }
    }//bohe

    //compute (tx,ty) as Steiner point os ij1,ij2,ij3
    void ihoujin(int ij1,int ij2,int ij3){
        double ka,se,xz,yz;
        ka=(y1[ij2]-y1[ij1])/(x1[ij2]-x1[ij1]);
        se=y1[ij1]-ka*x1[ij1];
        xz=x1[ij2]-x1[ij1];
        yz=y1[ij2]-y1[ij1];
        if(y1[ij3]<ka*x1[ij3]+se && x1[ij1]>x1[ij2]){
            tx=x1[ij1]+Math.cos(pi/3.0)*xz+Math.sin(pi/3.0)*yz;
            ty=y1[ij1]-Math.sin(pi/3.0)*xz+Math.cos(pi/3.0)*yz;
        }
        if(y1[ij3]>ka*x1[ij3]+se && x1[ij1]<x1[ij2]){
            tx=x1[ij1]+Math.cos(pi/3.0)*xz+Math.sin(pi/3.0)*yz;
            ty=y1[ij1]-Math.sin(pi/3.0)*xz+Math.cos(pi/3.0)*yz;
        }
        if(y1[ij3]<ka*x1[ij3]+se && x1[ij1]<x1[ij2]){
            tx=x1[ij1]+Math.cos(-pi/3.0)*xz+Math.sin(-pi/3.0)*yz;
            ty=y1[ij1]-Math.sin(-pi/3.0)*xz+Math.cos(-pi/3.0)*yz;
        }
        if(y1[ij3]>ka*x1[ij3]+se && x1[ij1]>x1[ij2]){
            tx=x1[ij1]+Math.cos(-pi/3.0)*xz+Math.sin(-pi/3.0)*yz;
            ty=y1[ij1]-Math.sin(-pi/3.0)*xz+Math.cos(-pi/3.0)*yz;
        }
    }//ihoujin



    void musoubana(int mij1,int mij2,int mij3){
        double xc,yc,an,bn,mux,muy,rr;
        xc=(x1[mij1]+x1[mij2]+tx)/3.0;
        yc=(y1[mij1]+y1[mij2]+ty)/3.0;
        rr=d(x1[mij1],y1[mij1],xc,yc);
        x1[mij1]=x1[mij1]-xc;
        y1[mij1]=y1[mij1]-yc;
        x1[mij2]=x1[mij2]-xc;
        y1[mij2]=y1[mij2]-yc;
        x1[mij3]=x1[mij3]-xc;
        y1[mij3]=y1[mij3]-yc;
        tx=tx-xc;
        ty=ty-yc;
        an=(y1[mij3]-ty)/(x1[mij3]-tx);
        bn=ty-an*tx;
        if(tx<x1[mij3]){
            x1[NN]=(-an*bn+jou(an*an*bn*bn-(bn*bn-rr*rr)*(1.0+an*an),0.5))/(1.0+an*an)+0.0001*Math.cos(pi*2.0*rand());
            y1[NN]=an*x1[NN]+bn+0.0001*Math.sin(pi*2.0*rand());
            sl[NN]=1;
            NN++;
        }
        else{
            x1[NN]=(-an*bn-jou(an*an*bn*bn-(bn*bn-rr*rr)*(1.0+an*an),0.5))/(1.0+an*an)+0.0001*Math.cos(pi*2.0*rand());
            y1[NN]=an*x1[NN]+bn+0.0001*Math.sin(pi*2.0*rand());
            sl[NN]=1;
            NN++;
        }
        x1[mij1]=x1[mij1]+xc;
        y1[mij1]=y1[mij1]+yc;
        x1[mij2]=x1[mij2]+xc;
        y1[mij2]=y1[mij2]+yc;
        x1[mij3]=x1[mij3]+xc;
        y1[mij3]=y1[mij3]+yc;
        tx=tx+xc;
        ty=ty+yc;
        x1[NN-1]=x1[NN-1]+xc;
        y1[NN-1]=y1[NN-1]+yc;
    }//musoubana


    void msbn2(int msbn,int mij1,int mij2,int mij3){
        double xc,yc,an,bn,mux,muy,rr;
        xc=(x1[mij1]+x1[mij2]+tx)/3.0;
        yc=(y1[mij1]+y1[mij2]+ty)/3.0;
        rr=d(x1[mij1],y1[mij1],xc,yc);
        x1[mij1]=x1[mij1]-xc;
        y1[mij1]=y1[mij1]-yc;
        x1[mij2]=x1[mij2]-xc;
        y1[mij2]=y1[mij2]-yc;
        x1[mij3]=x1[mij3]-xc;
        y1[mij3]=y1[mij3]-yc;
        tx=tx-xc;
        ty=ty-yc;
        an=(y1[mij3]-ty)/(x1[mij3]-tx);
        bn=ty-an*tx;
        if(tx<x1[mij3]){
            x1[msbn]=(-an*bn+jou(an*an*bn*bn-(bn*bn-rr*rr)*(1.0+an*an),0.5))/(1.0+an*an)+0.0001*Math.cos(pi*2.0*rand());
            y1[msbn]=an*x1[msbn]+bn+0.0001*Math.sin(pi*2.0*rand());
            sl[msbn]=1;
        }
        else{
            x1[msbn]=(-an*bn-jou(an*an*bn*bn-(bn*bn-rr*rr)*(1.0+an*an),0.5))/(1.0+an*an)+0.0001*Math.cos(pi*2.0*rand());
            y1[msbn]=an*x1[msbn]+bn+0.0001*Math.sin(pi*2.0*rand());
            sl[msbn]=1;
        }
        x1[mij1]=x1[mij1]+xc;
        y1[mij1]=y1[mij1]+yc;
        x1[mij2]=x1[mij2]+xc;
        y1[mij2]=y1[mij2]+yc;
        x1[mij3]=x1[mij3]+xc;
        y1[mij3]=y1[mij3]+yc;
        tx=tx+xc;
        ty=ty+yc;
        x1[msbn]=x1[msbn]+xc;
        y1[msbn]=y1[msbn]+yc;
    }//msbn2

    void tase1(int it1){
        int qint;
        double xx2,yy2,qa,qb,qc,qw,minq;
        xx=x1[connect[it1][0]];
        yy=y1[connect[it1][0]];
        xx2=x1[connect[it1][1]];
        yy2=y1[connect[it1][1]];
        qa=d(xx,yy,xx2,yy2);
        qb=d(xx,yy,x1[it1],y1[it1]);
        qc=d(xx2,yy2,x1[it1],y1[it1]);
        qw=arccosaw((qb*qb+qc*qc-qa*qa)/(2.0*qb*qc));
        minq=qw;
        qint=1;
        xx=x1[connect[it1][1]];
        yy=y1[connect[it1][1]];
        xx2=x1[connect[it1][2]];
        yy2=y1[connect[it1][2]];
        qa=d(xx,yy,xx2,yy2);
        qb=d(xx,yy,x1[it1],y1[it1]);
        qc=d(xx2,yy2,x1[it1],y1[it1]);
        qw=arccosaw((qb*qb+qc*qc-qa*qa)/(2.0*qb*qc));
        if(qw<minq){
            minq=qw;
            qint=2;
        }
        xx=x1[connect[it1][2]];
        yy=y1[connect[it1][2]];
        xx2=x1[connect[it1][0]];
        yy2=y1[connect[it1][0]];
        qa=d(xx,yy,xx2,yy2);
        qb=d(xx,yy,x1[it1],y1[it1]);
        qc=d(xx2,yy2,x1[it1],y1[it1]);
        qw=arccosaw((qb*qb+qc*qc-qa*qa)/(2.0*qb*qc));
        if(qw<minq){
            minq=qw;
            qint=3;
        }
        if(qint==1){
            ihoujin(it1,connect[it1][0],connect[it1][1]);
            musoubana(it1,connect[it1][0],connect[it1][1]);
        }
        if(qint==2){
            ihoujin(it1,connect[it1][1],connect[it1][2]);
            musoubana(it1,connect[it1][1],connect[it1][2]);
        }
        if(qint==3){
            ihoujin(it1,connect[it1][2],connect[it1][0]);
            musoubana(it1,connect[it1][2],connect[it1][0]);
        }
    }//tase1

    void tase2(int it2){
        ihoujin(it2,connect[it2][0],connect[it2][1]);
        musoubana(it2,connect[it2][0],connect[it2][1]);
    }//tase2

    void tuika(){
        int tlabel,tra,tra2;
        tlabel=0;
        tra=0;
        tra2=0;
        while(tlabel==0 && tra<10){
            tra++;
            int ter=0;
            for(int it=0;it<N;it++){
                if(cn[it]>2){
                    tra2++;
                    ter=1;
                    tase1(it);
                    mst();
                    hantei();
                    if(NN>2*N-2){
                        break;
                    }
                }//cn[it]==3
            }//it
            for(int it=0;it<N;it++){
                if(cn[it]==2){
                    double xx2,yy2,qa,qb,qc,qw;
                    xx=x1[connect[it][0]];
                    yy=y1[connect[it][0]];
                    xx2=x1[connect[it][1]];
                    yy2=y1[connect[it][1]];
                    qa=d(xx,yy,xx2,yy2);
                    qb=d(xx,yy,x1[it],y1[it]);
                    qc=d(xx2,yy2,x1[it],y1[it]);
                    qw=arccosaw((qb*qb+qc*qc-qa*qa)/(2.0*qb*qc));
                    if(qw<2.0*pi/3.0){
                        tra2++;
                        ter=2;
                        tase2(it);
                        mst();
                        hantei();
                        if(NN>2*N-2){
                            break;
                        }
                    }//qw>2.0*pi/3.0
                }//cn[it]==2
            }//it
            if(ter==0){
                tlabel=1;
            }
        }//tlabel
        if(tra2>0){
            bohe();
            mst();
            hantei();
        }
    }//tuika

    void mrlonely(){
        int qint;
        double xx2,yy2,qa,qb,qc,qw,maxq,qwe;
        int tlabel,tra,tra2;
        tlabel=0;
        tra=0;
        tra2=0;
        while(tlabel==0){
            tra++;
            int ter=0;
            for(int it1=N;it1<NN;it1++){
                if(cn[it1]==3){
                    xx=x1[connect[it1][0]];
                    yy=y1[connect[it1][0]];
                    xx2=x1[connect[it1][1]];
                    yy2=y1[connect[it1][1]];
                    qa=d(xx,yy,xx2,yy2);
                    qb=d(xx,yy,x1[it1],y1[it1]);
                    qc=d(xx2,yy2,x1[it1],y1[it1]);
                    qw=arccosaw((qb*qb+qc*qc-qa*qa)/(2.0*qb*qc));
                    qwe=d(qw,0.0,2.0*pi/3.0,0.0);
                    maxq=qwe;
                    xx=x1[connect[it1][1]];
                    yy=y1[connect[it1][1]];
                    xx2=x1[connect[it1][2]];
                    yy2=y1[connect[it1][2]];
                    qa=d(xx,yy,xx2,yy2);
                    qb=d(xx,yy,x1[it1],y1[it1]);
                    qc=d(xx2,yy2,x1[it1],y1[it1]);
                    qw=arccosaw((qb*qb+qc*qc-qa*qa)/(2.0*qb*qc));
                    qwe=d(qw,0.0,2.0*pi/3.0,0.0);
                    if(qwe>maxq){
                        maxq=qwe;
                    }
                    xx=x1[connect[it1][2]];
                    yy=y1[connect[it1][2]];
                    xx2=x1[connect[it1][0]];
                    yy2=y1[connect[it1][0]];
                    qa=d(xx,yy,xx2,yy2);
                    qb=d(xx,yy,x1[it1],y1[it1]);
                    qc=d(xx2,yy2,x1[it1],y1[it1]);
                    qw=arccosaw((qb*qb+qc*qc-qa*qa)/(2.0*qb*qc));
                    qwe=d(qw,0.0,2.0*pi/3.0,0.0);
                    if(qwe>maxq){
                        maxq=qwe;
                    }
                    if(maxq>pi/180.0){
                        ter++;
                        ihoujin(connect[it1][0],connect[it1][1],connect[it1][2]);
                        msbn2(it1,connect[it1][0],connect[it1][1],connect[it1][2]);
                        mst();
                        hantei();
                    }//maxq>pi/180.0
                }//cn[it1]==2
            }//it1
            if(ter==0){
                tlabel=1;
            }
        }//tlabel
        if(tra2>0){
            bohe();
            mst();
            hantei();
        }
    }//mrlonely

    public void hantei(){
        int ih;
        dd2=moku();
        if(dd2<mind){
            counter2++;
            mind=dd2;
	    for(ih=0;ih<NN;ih++){
	        xmin[ih]=x1[ih];
	        ymin[ih]=y1[ih];
	        slmin[ih]=sl[ih];
	    }
            minNN=NN;
	    for(ih=0;ih<NN-1;ih++){
	        e1min[ih]=e1[ih];
	        e2min[ih]=e2[ih];
	    }
	    repaint();
        }
    }//hantei

    public void run(){
        pi=3.1415926535897932384626;
        counter2=0;
        xx=0.0;
        yy=0.0;
        steinerlabel=0;
        for(k=0;k<N;k++){
            x1[k]=rand()*(haba-30)+15;
            y1[k]=rand()*(taka-45)+30;
            sl[k]=0;
            w1[k]=arcsinaw((y1[k]-yy)/d(x1[k],y1[k],xx,yy))+pi/2;
            s[k]=jou(x1[k]*x1[k]+y1[k]*y1[k],0.5);
        }
        heapv(x1,y1,w1,N);

        for(k=0;k<N;k++){
            x2[k]=x1[k];
            y2[k]=y1[k];
        }

        ch();

        mind=99999.9;
        tim=0;
        for(;;){
	    tim++;
	    timlabel=0;
	    if(N>20){
	        if(tim % 3==0){
        	    timlabel=1;
                }
	    }
            if(N>9 && N<21){
	        if(tim % 30==0){
		    timlabel=1;
	        }
            }
            if(N<10){
	        if(tim % 100==0){
		    timlabel=1;
	        }
	    }
            if(timlabel==1){
                repaint();
            }
            sco=0;
            NN=N;
            for(k=0;k<N-2;k++){
                if(rand()<0.5){
                    int chrule,br2;
                    double x1kouho=100.0,y1kouho=100.0;
                    chrule=0;
                    while(chrule==0){
                        x1kouho=rand()*(haba-30)+15;
                        y1kouho=rand()*(taka-30)+15;
                        br2=0;
                        for(h=0;h<coch;h++){
                            if(y1kouho>aa[h]*x1kouho+bb[h]){
                                br2=1;
                            }
                        }
                        for(h=0;h<coch2;h++){
                            if(y1kouho<aa2[h]*x1kouho+bb2[h]){
                                br2=1;
                            }
                        }
                        if(br2==0){
                            chrule=1;
                        }
                    }//chrule
                    x1[N+sco]=x1kouho;
                    y1[N+sco]=y1kouho;
                    sl[N+sco]=1;
                    sco++;
                    NN=N+sco;
                }
            }

            mst();
            hantei();
            bohe();
            mst();
            bohe();
            mst();
            hantei();
            mrlonely();
            tuika();
        }//next;;
    }//run

    public void update(Graphics g){
        paint(g);
    }
    public void paint(java.awt.Graphics g){
        int dk;
        g.setColor(col1);
        g.fillRect(1,1,haba,taka);
        for(dk=0;dk<NN-1;dk++){
            g.drawLine((int)x1[e1[dk]],(int)y1[e1[dk]],(int)x1[e2[dk]],(int)y1[e2[dk]]);
        }
        g.setColor(cl[0]);
        for(dk=0;dk<minNN;dk++){
            if(slmin[dk]==0){
               g.setColor(cl[0]);
                g.fillOval((int)xmin[dk]-3,(int)ymin[dk]-3,6,6);
            }
            else{
               g.setColor(cl[2]);
                g.drawRect((int)xmin[dk]-5,(int)ymin[dk]-5,10,10);
            }
        }
        g.setColor(cl[1]);
        for(dk=0;dk<minNN-1;dk++){
            g.drawLine((int)xmin[e1min[dk]],(int)ymin[e1min[dk]],(int)xmin[e2min[dk]],(int)ymin[e2min[dk]]);
        }
        g.drawString("N="+N,15,15);
        g.drawString("M="+(minNN-N),15,30);
        g.drawString("N+M="+minNN,65,15);
        g.drawString("counter="+tim,65,30);
        g.drawString("d="+mind,145,15);
        g.drawString("counter2="+counter2,145,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);
    }//paint

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