import java.awt.Graphics;
import java.applet.Applet;
import java.awt.Color;
import java.awt.*;
public class hakicli extends java.applet.Applet{
  Point[] p = new Point[100];
  Color col1,col2,col3;
  int N,taka,haba,ni,nj,co2,n;
  int k,i,j,l,co,mink,minl;
  double di2,di,cp2,cpx,ys,t;
  double x0,y0,xx,yy,xa1=0,ya1=0,yy2,ldd,minld;
  double di4,di3,cp3,cpx3,ys3,t2,ds,us,mind;
  double y20,y21,sa0,sa1;
  int br,br2,u,k2;
  int xz,xz2,yz,yz2,label;
  String NS,habaS,takaS;
  double Nd,takad,habad;
  Color cl[]=new Color[13];
  double kx[]=new double[100];
  double ky[]=new double[100];
  double kz[]=new double[100];


  int frog[]=new int[1000];

  double pa[]=new double[1000];
  double paj[]=new double[1000];
  double pai[]=new double[1000];
  int pan[]=new int[1000];

  double ei[]=new double[1000];
  double ej[]=new double[1000];
  double ed[]=new double[1000];
  int en[]=new int[1000];

  public double dou(String dous){
    double dou1;
    dou1 = (Double.valueOf(dous)).doubleValue();
    return dou1;
  }
  public double rand(){
    double rand1;
    rand1=Math.random();
    return rand1;
  }
  public void init(){
    col1=Color.black;
    col2=Color.yellow;
    col3=Color.green;
    cl[0]=Color.white;
    cl[1]=Color.red;
    cl[2]=new Color(199,111,238);
    takaS=getParameter("takap");
    habaS=getParameter("habap");
    NS=getParameter("Np");
    habad=dou(habaS);
    takad=dou(takaS);
    Nd=dou(NS);
    if(Nd==20){
      Nd=3+47*rand();
    }
    haba=(int)habad;
    taka=(int)takad;
    N=(int)Nd;
  }
  double x1[]=new double[100];
  double y1[]=new double[100];
  int x[]=new int[100];
  int y[]=new int[100];
  double s[]=new double[100];
  String sss[]=new String[100];
  public double jou(double a,double b){
    double jou1;
    jou1=Math.pow(a,b);
    return jou1;
  }
  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 void paint(java.awt.Graphics g){
    g.setColor(col1);
    g.fillRect(1,1,haba,taka);
    g.setColor(col2);
    Point old,current;
    N=n;
    for(k=0;k<N;k++){
      x1[k]=p[k].x+Math.cos(k*1.1)+k*0.0001;
      y1[k]=p[k].y+Math.sin(k*1.1)+k*0.001;
      x[k]=(int)(x1[k]+0.5);
      y[k]=(int)(y1[k]+0.5);
      s[k]=jou(x1[k]*x1[k]+y1[k]*y1[k],0.5);
      g.fillOval(x[k]-4,y[k]-4,8,8);
    }
    co=0;
    g.setColor(cl[1]);
    for(i=1;i<=N-1;i++){
      for(j=i+1;j<=N;j++){
        di2=(y1[i-1]-y1[j-1])/(x1[i-1]-x1[j-1]);
        di=-1/di2;
        cp2=(y1[i-1]+y1[j-1])/2;
        cpx=(x1[i-1]+x1[j-1])/2;
        ys=cp2-cpx*di;
        t=jou(x1[i-1]-x1[j-1],2)+jou(y1[i-1]-y1[j-1],2);
        l=1;
        kx[l-1]=-10*haba;ky[l-1]=-10*di*haba+ys;
        for(k=1;k<=N;k++){
          if(k!=i && k!=j){
            di4=(y1[i-1]-y1[k-1])/(x1[i-1]-x1[k-1]);
            di3=-1/di4;
            cp3=(y1[i-1]+y1[k-1])/2;
            cpx3=(x1[i-1]+x1[k-1])/2;
            ys3=cp3-cpx3*di3;
            t2=jou(x1[i-1]-x1[k-1],2)+jou(y1[i-1]-y1[k-1],2);
              l++;
              kx[l-1]=(ys3-ys)/(di-di3);
              ky[l-1]=di*kx[l-1]+ys;
          }//if(k!=i && k!=j)
        }//next k
          l++;
          kx[l-1]=11*haba;ky[l-1]=11*di*haba+ys;
          for(u=1;u<=l;u++){
            kz[u-1]=0;
          }
          heapv(kx,ky,kz,l);
          for(k=1;k<=l-1;k++){
            k2=k+1;
            xx=(kx[k-1]+kx[k2-1])/2;
            yy2=di*xx+ys;
            ds=jou(xx-x1[i-1],2)+jou(yy2-y1[i-1],2);
            br2=0;
            for(u=1;u<=N;u++){
              if(u!=i && u!=j){
                us=jou(xx-x1[u-1],2)+jou(yy2-y1[u-1],2);
                if(us<ds){
                  br2=br2+1;
                }
              }
            }//next u
            if(br2==0){
              xz=(int)(kx[k-1]+0.5);
              xz2=(int)(kx[k2-1]+0.5);
              yz=(int)(ky[k-1]+0.5);
              yz2=(int)(ky[k2-1]+0.5);
              g.drawLine((int)x1[i-1],(int)y1[i-1],(int)x1[j-1],(int)y1[j-1]);
              ei[co]=i-1;
              ej[co]=j-1;
              ed[co]=jou(jou(x1[i-1]-x1[j-1],2)+jou(y1[i-1]-y1[j-1],2),0.5);
              co++;
            }//if br2<3
          }//next k
      }//next j
    }//next i

    heapv(ed,ei,ej,co);

    minld=999999.9;
    minl=9999;
    for(l=0;l<N;l++){
        ldd=0.0;
        g.setColor(cl[0]);
        x0=x1[l];
        y0=y1[l];
        for(i=0;i<co;i++){
            en[i]=0;
        }
        for(i=0;i<N;i++){
            if(i!=l){
                frog[i]=0;
            }
        }
        frog[l]=1;

        co2=0;
        for(i=0;i<co;i++){
            if(frog[(int)ei[i]]==1 && frog[(int)ej[i]]==0 && en[i]==0){
                co2++;
                pa[co2-1]=ed[i];
                pai[co2-1]=ei[i];
                paj[co2-1]=ej[i];
                pan[co2-1]=i;
                en[i]=1;
            }
            if(frog[(int)ei[i]]==0 && frog[(int)ej[i]]==1 && en[i]==0){
                co2++;
                pa[co2-1]=ed[i];
                pai[co2-1]=ej[i];
                paj[co2-1]=ei[i];
                pan[co2-1]=i;
                en[i]=1;
            }
        }//i

        for(i=0;i<N;i++){
            if(i!=l){
                mind=99999.9;
                mink=9999;
                for(j=0;j<co2;j++){
                    if(frog[(int)ei[pan[j]]]+frog[(int)ej[pan[j]]]==1){
                        if(pa[j]<mind){
                            mind=pa[j];
                            mink=j;
                        }
                    }
                }//j
                ldd=ldd+pa[mink];
                frog[(int)ej[pan[mink]]]=1;
                frog[(int)ei[pan[mink]]]=1;
                for(j=mink;j<co2-1;j++){
                    pa[j]=pa[j+1];
                    pai[j]=pai[j+1];
                    paj[j]=paj[j+1];
                    pan[j]=pan[j+1];
                }
                co2--;
                for(k=0;k<co;k++){
                    if(frog[(int)ei[k]]==1 && frog[(int)ej[k]]==0 && en[k]==0){
                        co2++;
                        pa[co2-1]=ed[k]+mind;
                        pai[co2-1]=ei[k];
                        paj[co2-1]=ej[k];
                        pan[co2-1]=k;
                        en[k]=1;
                    }
                    if(frog[(int)ei[k]]==0 && frog[(int)ej[k]]==1 && en[k]==0){
                        co2++;
                        pa[co2-1]=ed[k]+mind;
                        pai[co2-1]=ej[k];
                        paj[co2-1]=ei[k];
                        pan[co2-1]=k;
                        en[k]=1;
                    }
                }//k
            }//i!=l
        }//i<N-1
        if(ldd<minld){
            minld=ldd;
            minl=l;
        }
    }//l

    l=minl;
        ldd=0.0;
        g.setColor(cl[0]);
        x0=x1[l];
        y0=y1[l];
        g.drawOval((int)x0-7,(int)y0-7,14,14);
        for(i=0;i<co;i++){
            en[i]=0;
        }
        for(i=0;i<N;i++){
            if(i!=l){
                frog[i]=0;
            }
        }
        frog[l]=1;

        co2=0;
        for(i=0;i<co;i++){
            if(frog[(int)ei[i]]==1 && frog[(int)ej[i]]==0 && en[i]==0){
                co2++;
                pa[co2-1]=ed[i];
                pai[co2-1]=ei[i];
                paj[co2-1]=ej[i];
                pan[co2-1]=i;
                en[i]=1;
            }
            if(frog[(int)ei[i]]==0 && frog[(int)ej[i]]==1 && en[i]==0){
                co2++;
                pa[co2-1]=ed[i];
                pai[co2-1]=ej[i];
                paj[co2-1]=ei[i];
                pan[co2-1]=i;
                en[i]=1;
            }
        }//i

        for(i=0;i<N;i++){
            if(i!=l){
                mind=99999.9;
                mink=9999;
                for(j=0;j<co2;j++){
                    if(frog[(int)ei[pan[j]]]+frog[(int)ej[pan[j]]]==1){
                        if(pa[j]<mind){
                            mind=pa[j];
                            mink=j;
                        }
                    }
                }//j
                g.drawLine((int)x1[(int)ei[pan[mink]]],(int)y1[(int)ei[pan[mink]]],(int)x1[(int)ej[pan[mink]]],(int)y1[(int)ej[pan[mink]]]);
                frog[(int)ej[pan[mink]]]=1;
                frog[(int)ei[pan[mink]]]=1;
                for(j=mink;j<co2-1;j++){
                    pa[j]=pa[j+1];
                    pai[j]=pai[j+1];
                    paj[j]=paj[j+1];
                    pan[j]=pan[j+1];
                }
                co2--;
                for(k=0;k<co;k++){
                    if(frog[(int)ei[k]]==1 && frog[(int)ej[k]]==0 && en[k]==0){
                        co2++;
                        pa[co2-1]=ed[k]+mind;
                        pai[co2-1]=ei[k];
                        paj[co2-1]=ej[k];
                        pan[co2-1]=k;
                        en[k]=1;
                    }
                    if(frog[(int)ei[k]]==0 && frog[(int)ej[k]]==1 && en[k]==0){
                        co2++;
                        pa[co2-1]=ed[k]+mind;
                        pai[co2-1]=ej[k];
                        paj[co2-1]=ei[k];
                        pan[co2-1]=k;
                        en[k]=1;
                    }
                }//k
            }//i!=l
        }//i<N-1

    g.drawString("N="+N,15,15);
  }
  public boolean mouseDown(Event evt, int x, int y) {
    if(n<30){
      p[n] = new Point(x,y); n++;
    }
    else{
      n=0;
    }
    repaint();
    return true;
  }
}