import java.awt.Graphics;
import java.applet.Applet;
import java.awt.Color;
public class voro extends java.applet.Applet{
  Color col1,col2,col3;
  int N,taka,haba;
  int k,i,j,l;
  double di2,di,cp2,cpx,ys,t;
  double x0,y0,xx,yy,xa1=0,ya1=0,yy2;
  double di4,di3,cp3,cpx3,ys3,t2,ds,us;
  double y20,y21,sa0,sa1,sa2,sa3,sa4,sa5;
  int sa6,br,br2,u,k2;
  int xz,xz2,yz,yz2;
  String NS,habaS,takaS;
  double Nd,takad,habad;
  double kx[]=new double[100];
  double ky[]=new double[100];
  double kz[]=new double[100];

  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.white;
    takaS=getParameter("takap");
    habaS=getParameter("habap");
    NS=getParameter("Np");
    habad=dou(habaS);
    takad=dou(takaS);
    Nd=dou(NS);
    haba=(int)habad;
    taka=(int)takad;
    N=(int)Nd;
    if(N==20){
      N=4+(int)(46*rand());
    }
  }
  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;
  }


  //order by such that te1[0]<te1[1]<te1[2]...
  //te1の小さい順に並び替える
  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
  }

  //main function
  //main関数
  public void paint(java.awt.Graphics g){
    g.setColor(col1);
    g.fillRect(1,1,haba,taka);
    g.setColor(col2);
    g.drawString("N="+N,15,15);
    for(k=0;k<N;k++){
      x1[k]=rand()*(haba-30)+15;
      y1[k]=rand()*(taka-30)+15;
      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]-2,y[k]-2,4,4);
    }
    g.setColor(col3);
    for(i=1;i<=N-1;i++){
      for(j=i+1;j<=N;j++){
        //consider the bisector(perpendicular at midpoint) between i and j
        br=0;//ラベル label
        di2=(y1[i-1]-y1[j-1])/(x1[i-1]-x1[j-1]);//iとjを結ぶ線の傾き the slope the line segment from i to j
        di=-1/di2;//iとjの垂直二等分線の傾き the slope of bisector(perpendicular at midpoint) between i and j
        cp2=(y1[i-1]+y1[j-1])/2;//iとjの中点のy座標  y-coordinate of midpoint of i and j
        cpx=(x1[i-1]+x1[j-1])/2;//iとjの中点のx座標  x-coordinate of midpoint of i and j
        ys=cp2-cpx*di;//iとjの垂直二等分線のy切片  intercept of the bisector(perpendicular at midpoint) between i and j
        //Now, y = di * x +ys is the bisector(perpendicular at midpoint) between i and j.
        //So, every point (x,y) on this line has a property.
            //distance between i and (x,y) equals to the distance between j and (x,y).
        //So we can obtain region V(a_i) = {x|d(x,a_i)<=d(x,a_j) for j not i}, in this case, j is fixed.
        //Voronoi euqation is V(a_i) = {x|d(x,a_i)<=d(x,a_j) for all j not i}, in this case j is not fixed, for all j not i.
        //So, we must check line segments(group of points) on this bisector is nearer than any other j(not fixed, this j becomes k and u at later for-loop) 
        // we do this check loop- for(u=1;u<=N;u++){//uはi,j以外  u<>i, u<>j

        //Now, what are line segments(group of points)?
        // We want compare with any other j, So line segments are obtained from intersection between this bisector and the bisector of i and k(k is not i,j).

        t=jou(x1[i-1]-x1[j-1],2)+jou(y1[i-1]-y1[j-1],2);//iとjの距離  distance between i and j
        //takaは画面の高さ、habaは画面の幅 taka is the hight, haba is width of the screen, respectively

        //if intercept>0 and <(the hight of the screen) then the start point of the bisector is (0,ys)
        if(ys>0 && ys<taka){//切片が画面の高さより小さいのでiとjの垂直二等分線の始点は(0,ys)になる。
          x0=0;y0=ys;
        }
        else{//ys>0 && ys<taka){切片が画面外  ys<0 or ys> the hight of the screen
          if(di>0){//傾きが正なので、垂直二等分線の始点は(-ys/di,0)になる。 if slope>0 then the start point is (-ys/di,0)
            x0=-ys/di;y0=0;
          }
          else{//傾きが負なので、垂直二等分線の始点は下記になる。 if slope<0 then the start point is ((taka-ys)/di,taka)
            x0=(taka-ys)/di;
            y0=taka;
          }
        }
        yy=di*haba+ys;//画面の右端でのyの値 yy is the y-coordinate at x= the width of the screen
        if(yy>0 && yy<taka){//yyが（0,taka）の間にある場合、垂直二等分線の終点（右端）は(haba,yy)になる。 if yy>0 and yy<the hight of the screen then the end point of the bisector(perpendicular at midpoint) between i and j is (width of the screen,yy)
          xa1=haba;ya1=yy;
        }
        else{//yyが（0,taka）にない場合  yy<0 or yy> the hight of the screen
          if(di>0){//傾きが0より大きい場合  slope>0
            xa1=(taka-ys)/di;ya1=taka;
          }
          else{//slope<0
            xa1=-ys/di;
            ya1=0;
          }
        }

        //calculate the intersection of the two bisectors (i,j) and (i,k)
        //first intersection is the start point of the bisector between i and j
        //i,jの垂直二等分線とi,kの垂直二等分線を求めていく。
        //交点の最初はi,jの垂直二等分線の左端とする。（もちろん交点ではないが計算の都合上）
        l=1;//ijの垂直二等分線の左端を配列に記憶する
        kx[l-1]=x0;ky[l-1]=y0;//i,jの垂直二等分線の左端  start point of the bisector between i and j
        sa2=x1[j-1]-x1[i-1];//iとjのxの差  difference of x between i and j
        sa4=y1[j-1]-y1[i-1];//iとjのyの差  difference of y between i and j

        //calculate the intersection of the two bisectors (i,j) and (i,k), k is not i,j
        for(k=1;k<=N;k++){//iとkの垂直二等分線について順次計算していく  k=1,...,n
          if(k!=i && k!=j){//kはi,j以外 k is not i and not j
            di4=(y1[i-1]-y1[k-1])/(x1[i-1]-x1[k-1]);//i,kを結ぶ線の傾き  slope of the line connecting two points i and k
            di3=-1/di4;//i,kの垂直二等分線の傾き slope of the bisector between i and k
            cp3=(y1[i-1]+y1[k-1])/2;//i,kの中点のy座標  y-cooridnate of the midpoint between i and k
            cpx3=(x1[i-1]+x1[k-1])/2;//i,kの中点のx座標  x-cooridnate of the midpoint between i and k
            ys3=cp3-cpx3*di3;//垂直二等分線の切片  intercept of the bisector between i and k
            //Now, y = di3 * x +ys3 is the bisector(perpendicular at midpoint) between i and k(k is not i,j).

            t2=jou(x1[i-1]-x1[k-1],2)+jou(y1[i-1]-y1[k-1],2);//i,kの距離  the distance between i and k
            y20=di3*x0+ys3;//i,kの垂直二等分線の左端(この左端はi,jの左端(x座標))のy座標  y-coordinate of the start(this start point is the start point(x-coordinate) of the bisector between i and j) point of the bisector between i and k
            y21=di3*xa1+ys3;//i,kの垂直二等分線の右端(i,jの二等分線の)のｙ座標  x-coordinate of the start(this start point is the start point(x-coordinate) of the bisector between i and j) point of the bisector between i and k
            sa0=y0-y20;//左端での両二等分線のy座標の差 the difference of the two y-coordinates at the start point
            sa1=ya1-y21;//右端での両二等分線のy座標の差 the difference of the two y-coordinates at the end point
            sa3=x1[k-1]-x1[i-1];//i,kのx座標の差  the difference of x-coordinates between i and k
            sa5=y1[k-1]-y1[i-1];//i,kのy座標の差  the difference of y-coordinates between i and k
            if(sa2*sa3>0 && sa4*sa5>0){//iからみて（iを原点として）jとkが第一または第三象限にある場合  From the view point of the i(set the point of i to the point of origin, that is, x_i=0, y_i=0), x_j*y_j>0 and x_k*y_k>0 then 
              sa6=1;//sa6 is a flag
            }
            else{
              sa6=0;
            }
            if(sa0*sa1>0 && t>t2 && sa6==1){//j,kもiからみて同じ方向(象限)にあり、画面内ではij、ikの垂直二等分線は交わらず、kの方がiに近い  From the view of i, if j and k is same direction(the signs of x and y are same), and two bisectors (i,j) and (i,k) is not cross inside the screen, and k is closer to i than j then 
              br=1;//i,jの垂直二等分線は画面内にひかれないので、breakする。  then the bisector of (i,j) doesn't appear inside the screen  -> break
              break;
            }
            if(sa0*sa1<0 || t<t2 || sa6!=0){//上記以外  case else
              if(sa0*sa1<0 || t>t2){//ij,ikの垂直二等分線に画面内で交点があり、jがkよりiに近い  there is the intersection inside the screen and j is closer to i than k
                l++;//交点を配列に記憶する calculate the intersection
                kx[l-1]=(ys3-ys)/(di-di3);
                ky[l-1]=di*kx[l-1]+ys;
                //Now (kx,ky) is intersection between bisector (i,j) and bisector (i,k)
              }
            }
          }//if(k!=i && k!=j)
        }//next k
        if(br==0){
          l++;//ijの垂直二等分線の右端を配列に記憶する set the end point as the intersection
          kx[l-1]=xa1;
          ky[l-1]=ya1;
          for(u=1;u<=l;u++){//kzはダミー変数。とくに意味はない  kz are dummy variables they have no mean
            kz[u-1]=0;
          }
          //Now, on the bisector between i and j, y=di*x+ys, there are l intersections.
          //Sort these (kx,ky)
          heapv(kx,ky,kz,l);//kx(x座標)の小さい順に交点を並び替える。 order (kx,ky) such that kx[0]<kx[1]<....<kx[l-1]
          for(k=1;k<=l-1;k++){//交点と交点の間の線分でループする  consider the intervals between two intersections
            k2=k+1;//kが交点と交点を結ぶ線分の左端、k2が交点と交点を結ぶ線分の右端  k is the start point of the interval, k2 is the end point of the interval
            xx=(kx[k-1]+kx[k2-1])/2;//線分の中点のx座標  x-coordinate of the midpoint of the two intersections
            yy2=di*xx+ys;//上述のy座標  y-coordinate of the midpoint of the two intersections
            ds=jou(xx-x1[i-1],2)+jou(yy2-y1[i-1],2);//その中点からiまでの距離、すなわちjまでの距離  distance between the midpoint and i,  it is the same of the distance between the midpoint and j
            //if this distance, ds is shorter than any other distance to u(u is not i,j), this line segment OKs
            //Voronoi euqation: V(a_i) = {x|d(x,a_i)<=d(x,a_j) for all j not i}, in this case j is not fixed, for all j not i.
            br2=0;//if this distance, ds is shorter than any other distance to u, br2 keeps 0.
            for(u=1;u<=N;u++){//uはi,j以外  u<>i, u<>j
              if(u!=i && u!=j){
                us=jou(xx-x1[u-1],2)+jou(yy2-y1[u-1],2);//中点からuまでの距離  the distance between the midpoint and u
                if(us<ds){//uまでの距離がjまでの距離より小さければこの線分はひかれないのでフラグbrを付けてbreakする if the distance to u is smaller than the distance to j(i) then the bisector should not be drawn -> break
                  br2=1;
                  break;
                }
              }
            }//next u
            if(br2==0){//フラグを付けて線分をひく  if flag=0 then draw the interval
              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(xz,yz,xz2,yz2);
              break;//線分がひかれるとijの線分がもう一度ひかれることはないのでbreakする  the bisector should be draw just once -> break
            }//if br2==0
          }//next k
        }//if br==0
      }//next j
    }//next i
  }
}