/*<APPLET CODE="CirclesPacking.class" width=720 height=420>
<param name=n0 value=0.0>
<param name=n1 value=0.785398163397>
<param name=n2 value=0.539012084453>
...
<param name=n200 value=0.840434362111>
</APPLET>
*/

import java.io.*;
import java.applet.*;
import java.awt.*;
import java.awt.event.*;

//CirclesPacking osztaly definicio

public class CirclesPacking extends Applet implements Runnable {
     Graphics g;
      // a korok kozeppontjat tarolja a "virtualis" negyzetben
     Coordinate origos[];
     //a kirajzolando korok kozeppontjait tarolja
     Coordinate realOrigos[];
     //a legjobb eredmeny kozeppontjait tarolja
     Coordinate best[];
     // a korok tulajdonsagait tarolja
     Circles circles;
     // a kezelofelulet elemeit tarolja
     CpControls controls;
     Thread CpThread = null;
     // a "virtuális" négyzet merete
     static final int wp=1000;
     // a mozgatas kezdeti merteke
     double step;
     // a mozgatas nagysagat ezzel osztom
     static final double div=1.5;
     // max ilyen kicsi lehet a mozgatas erteke
     static final double limit=0.01;
     // a korok aktualis teruletet tarolja
     double s;
     // az aktualis probalkozas szamat tarolja
     int t;
     // ebben a stringbe kerul a HTML fajbol atvett megfelelo parameter
     String bests;
     // igaz ha a Checkbox be van kapcsolva
     boolean view;
     //igaz ha az algoritmus fut
     boolean doing;

// a korok tulajdonsagait tartalmazo osztaly

public class Circles {
     int n;
     double r;
     int tr;

     public int getN() { return n; }
     public void setN(int n) { this.n=n; }
     public int getTr() { return tr; }
     public void setTr(int tr) { this.tr=tr; }
     public Circles(int n, int tr) { this.n=n; this.tr=tr; }
     public double getSurface() {
          if(n==1) { return (n*r*r*Math.PI); }
          else { return (n*r*r*Math.PI)/((wp+2*r)*(wp+2*r)); }
          }

     }

// a korok kozeppontjait tarolo osztaly

public class Coordinate {
     double x;
     double y;

     public Coordinate(double x, double y) { this.x=x; this.y=y; }

     }

// a kezelofelulet elemeit tarolo osztaly

public class CpControls extends Panel {
     TextField circlesN = new TextField(4);
     TextField circlesTr = new TextField(8);
     Checkbox view = new Checkbox(" Show me only the best results");

     public CpControls() {
          add(new Label("Number of circles:"));
          add(circlesN);
          add(new Label("Number of try-outs:"));
          add(circlesTr);
          add(new Button(" Start "));
          add(new Button(" Stop "));
          add(view);
          setBackground(Color.white);
          }
     }

// inicializalo fuggveny

public void init() {
     g=getGraphics();
     setLayout(new BorderLayout());
     controls=new CpControls();
     add("South", controls);
     setCircles(new Circles(9, 10));
     bests="0.0";
     s=0;
     t=0;
     view=true;
     doing=false;
     repaint();
     }

// a Start fuggveny

public void start() {
     CpThread = new Thread(this);
     CpThread.start();
     }

// ezt hivja meg a Start

public void run() {
     while(true) {
          if(doing==true) {
               examine();
               doing=false;
               }
          try {
               Thread.sleep(100);
               }
          catch(InterruptedException e) {
               }
          }
     }

// beallitja a circles objektum argumentumainak ertekeit

public void setCircles(Circles circles) {

     this.circles=circles;
     controls.circlesN.setText(""+circles.getN());
     controls.circlesTr.setText(""+circles.getTr());
     }

/* megvizsgalja es lekezeli a kulonleges eseteket,
meghivja a pontok mozgatasaert felelos movePoints() metodust
*/

public void examine() {
     double r=0;

     origos = new Coordinate[circles.n];
     realOrigos= new Coordinate[circles.n];
     best= new Coordinate[circles.n];
     if(circles.n==0) {
          s=0;
          repaint();
          }
     if(circles.n==1) {
          circles.r=0.5;
          s=circles.getSurface();
          repaint();
          }
     else if(circles.n>1) {
          for(int i=1; i<=circles.tr; ++i) {
               if(doing==false) {
                    break;
                    }
               t=i;
               movePoints();
               if(circles.r>r) {
                    r=circles.r;
                    s=circles.getSurface();
                    circlesDraw(best, 0);
                    }
               }
          }
     }

// veletlenszeruen elhelyezi a pontokat a "virtualis" negyzetben

public void randomPoints() {
     double x,y;

     for(int i=0; i<=(circles.n-1); ++i) {
          x=wp*Math.random();
          y=wp*Math.random();
          origos[i] = new Coordinate(x, y);
          }
     }

// a pontok mozgatasaert felelos metodus

public void movePoints() {
     boolean moved;
     double closest;
     double distance;
     double x, y;

     step=200;
     randomPoints();
     circles.r=(minimumDistance(origos)/2.0);
     if(circles.r==0.0) {
          do {
               randomPoints();
               circles.r=(minimumDistance(origos)/2.0);
               } while(circles.r==0.0);
          }
     do {
          if(doing==false) {
               break;
               }
          moved=false;
          for(int i=0; i<=(circles.n-1); ++i) {
               x=origos[i].x;
               y=origos[i].y;
               closest=nearestNeighbour(origos, i, x, y);
               x=origos[i].x+step;
               if(x>wp) { x=wp; }
               distance=nearestNeighbour(origos, i, x, y);
               if(distance>closest) {
                    origos[i].x=x;
                    moved=true;
                    closest=nearestNeighbour(origos, i, x, y);
                    }
               x=origos[i].x-step;
               y=origos[i].y;
               if(x<0) { x=0; }
               distance=nearestNeighbour(origos, i, x, y);
               if(distance>closest) {
                    origos[i].x=x;
                    moved=true;
                    closest=nearestNeighbour(origos, i, x, y);
                    }
               y=origos[i].y+step;
               x=origos[i].x;
               if(y>wp) { y=wp; }
               distance=nearestNeighbour(origos, i, x, y);
               if(distance>closest) {
                    origos[i].y=y;
                    moved=true;
                    closest=nearestNeighbour(origos, i, x, y);
                    }
               y=origos[i].y-step;
               x=origos[i].x;
               if(y<0) { y=0; }
               distance=nearestNeighbour(origos, i, x, y);
               if(distance>closest) {
                    origos[i].y=y;
                    moved=true;
                    }
               }
          if(moved==false ) { step/=div; }
          circles.r=(minimumDistance(origos)/2.0);
          circlesDraw(realOrigos, 370);
          } while(step>limit);
     }

// az adott ponthoz legkozelebb levo pont tavolsagat adja vissza

public double nearestNeighbour(Coordinate points[], int index, double a, double b) {
     double nearest;
     double dist;

     nearest=Math.sqrt(2*wp*wp);
     for(int j=0; j<=(circles.n-1); ++j) {
          if(index!=j) {
               dist=Math.sqrt(((a-points[j].x)*(a-points[j].x))
                    +((b-points[j].y)*(b-points[j].y)));
               if(dist<nearest)  { nearest=dist; }
               }
          }
     return nearest;
     }

// a pontok kozti legkissebb tavolsagot adja vissza

public double minimumDistance(Coordinate points[]) {
     double minDist;
     double dist;

     minDist=Math.sqrt(((points[0].x-points[1].x)*(points[0].x-points[1].x))
             +((points[0].y-points[1].y)*(points[0].y-points[1].y)));
     for(int i=0; i<=(circles.n-1); ++i) {
          for(int j=0; j<=(circles.n-1); ++j) {
               if(i != j) {
                    dist=Math.sqrt(((points[i].x-points[j].x)*(points[i].x-points[j].x))
                         +((points[i].y-points[j].y)*(points[i].y-points[j].y)));
                    if(dist<minDist)  { minDist=dist; }
                    }
               }
          }
     return minDist;
     }

/* az origos pontjait attranszformalja a realOrigos pontjaiva,
azaz a "virtualis" negyzetbol a valodi negyzetbe helyezi a pontokat
*/

public void transform(Coordinate points[]) {
     double rate;
     double x,y;

     rate=350/(wp+2*circles.r);
     for(int i=0; i<=(circles.n-1); ++i) {
          x=(rate*origos[i].x);
          y=(rate*origos[i].y);
          points[i]=new Coordinate(x,y);
          }
     }

// a korok kirajzolasat vegzi

public void circlesDraw (Coordinate points[], int shift) {
     int x,y;
     int d;

     setBackground(Color.white);
     if(shift==0 || (shift==370 && view==true)) {
          transform(points);
          g.setColor(Color.white);
          g.fillRect(0+shift-2, 0, 354, 354);
          g.setColor(Color.black);
          g.drawRect(0+shift, 0, 350, 350);
          d=(int) (minimumDistance(points));
          for(int i=0; i<=(circles.n-1); ++i) {
               x=(int) (points[i].x+d/2);
               y=(int) (points[i].y+d/2);
               g.setColor(Color.yellow);
               g.fillOval((x-d/2)+shift, y-d/2, d, d);
               g.setColor(Color.black);
               g.drawOval((x-d/2)+shift, y-d/2, d, d);
               g.fillOval(x-2+shift, y-2, 4, 4);
               }
          }
     else {
          g.setColor(Color.white);
          g.fillRect(370, 0, 352, 352);
          g.setColor(Color.black);
          g.drawRect(370, 0, 350, 350);
          }

     g.setColor(Color.white);
     g.fillRect(470,351,251,70);
     g.setColor(Color.black);
     g.drawString("Number of the present try-out: "+t, 470, 370);
     if(shift==0) {
          g.setColor(Color.white);
          g.fillRect(0,351,469,70);
          g.setColor(Color.black);
          g.drawString("Density: "+s, 10, 370);
          g.setColor(Color.red);
          if(circles.n<=200) {
               if(t==1) {
                    bests=getParameter("n"+circles.n);
                    }
               g.drawString("The best density known yet: "+bests,190, 370);
               }
          else {
               g.drawString("The best density known yet: unknown",190, 370);
               }
          }
     }

// szinten a korok rajzolasaert felelos

public void paint(Graphics g) {
     int x,y;
     int d;

     setBackground(Color.white);
     g.setColor(Color.black);
     g.drawRect(0, 0, 350, 350);
     g.drawRect(370, 0, 350, 350);
     g.drawString("Density: "+s, 10, 370);
     g.drawString("Number of the present try-out: "+t, 470, 370);
     if(circles.n==0) {
          bests=getParameter("n"+circles.n);
          }
     if(circles.n==1) {
          bests=getParameter("n"+circles.n);
          }
     g.setColor(Color.red);
     g.drawString("The best density known yet: "+bests,190, 370);

     if(circles.n==1) {
          g.setColor(Color.yellow);
          g.fillOval(0, 0, 350, 350);
          g.setColor(Color.black);
          g.drawOval(0, 0, 350, 350);
          g.fillOval(173, 173, 4, 4);
          if(view==true) {
               g.setColor(Color.yellow);
               g.fillOval(370, 0, 350, 350);
               g.setColor(Color.black);
               g.drawOval(370, 0, 350, 350);
               g.fillOval(543, 173, 4, 4);
               }
          }
     if(t>=1 && (circles.n>1)) {
          d=(int) (minimumDistance(best));
          for(int i=0; i<=(circles.n-1); ++i) {
               x=(int) (best[i].x+d/2);
               y=(int) (best[i].y+d/2);
               g.setColor(Color.yellow);
               g.fillOval(x-d/2, y-d/2, d, d);
               g.setColor(Color.black);
               g.drawOval(x-d/2, y-d/2, d, d);
               g.fillOval(x-2, y-2, 4, 4);
               }
          }
     if((t==circles.tr && view==true) && (circles.n>1)) {
          d=(int) (minimumDistance(realOrigos));
          for(int i=0; i<=(circles.n-1); ++i) {
               x=(int) (realOrigos[i].x+d/2);
               y=(int) (realOrigos[i].y+d/2);
               g.setColor(Color.yellow);
               g.fillOval((x-d/2)+370, y-d/2, d, d);
               g.setColor(Color.black);
               g.drawOval((x-d/2)+370, y-d/2, d, d);
               g.fillOval((x-2)+370, y-2, 4, 4);
               }
          }
     }

// lekezeli az esemenyeket

public boolean action(Event e, Object arg) {
     Checkbox id;

     if(e.target instanceof Button) {
          String label=(String) arg;
          if (label.equals(" Start ")) {
               circles.setN( Integer.parseInt(controls.circlesN.getText()));
               circles.setTr( Integer.parseInt(controls.circlesTr.getText()));
               setCircles(circles);
               doing=true;

               }
          else {
               doing=false;
               }
          }
     if(e.target instanceof Checkbox) {
          id = (Checkbox) e.target;
          if(id.getLabel() == " Show me only the best results") {
               if(id.getState()) {
                    view=false;
                    }
               else {
                    view=true;
                    }
               }
          }

     return true;
     }

}