import java.lang.*;
import java.applet.*;
import java.awt.*;
import java.util.*;

class Bod extends Object {
  double x;
  double y;
  Hashtable hrany;

  public Bod(Hashtable h,double x, double y) {
    this.x = x;
    this.y = y;
    h.put(new Integer(this.hashCode()),this);
    hrany = new Hashtable();
  }

  public Bod(double x, double y) {
    this.x = x;
    this.y = y;
    hrany = new Hashtable();
  }
  
  public Bod(int x, int y) {
    this.x = (double)x;
    this.y = (double)y;
    hrany = new Hashtable();
  }

  public double vzdalenost(Bod bod) {
    return Math.sqrt((x-bod.x)*(x-bod.x)+(y-bod.y)*(y-bod.y));
  }

  public void paint(Graphics g) {
    g.drawLine((int)x-2,(int)y-2,(int)x+2,(int)y+2);
    g.drawLine((int)x+2,(int)y-2,(int)x-2,(int)y+2);
  }
 
  public String toString() {
    return new String("x: "+x+", y: "+y);
  }

  public String toText() {
    int i = 0;
    String s = toString();
    Enumeration en = hrany.elements();
    while (en.hasMoreElements()) {
      i++;
      s = new String(s+"\n"+i+". "+(Hrana)en.nextElement());
    }
    return s;
  }
}

class Pbod extends Bod {
  Hashtable hrany;

  public Pbod(Hashtable h,double x,double y) {
    super(h,x,y);
    hrany = new Hashtable(); 
  }
  
  public Pbod(double x,double y) {
    super(x,y);
    hrany = new Hashtable();
  }  
 
  public void add(Hrana h) {
    hrany.put(new Integer(h.hashCode()),h);
  }

  public void delete(Hrana h) {
    //if (hrany==null) {
    //  System.out.println("Hrany nulove!!!");
    //  return;
    //}
    hrany.remove(new Integer(h.hashCode()));
    Voron.pbodToDelete.put(new Integer(this.hashCode()),this);
  }

  public void delete() {
    if (hrany==null) return;
    Enumeration en = hrany.elements();
    hrany = null; 
    Voron.pbody.remove(new Integer(this.hashCode()));
    while (en.hasMoreElements()) {
      Hrana h = (Hrana)en.nextElement();
      h.delete();
    }
  }
  
  public String toString() {
    int i = 0;
    String s = super.toString();
    Enumeration en = hrany.elements();
    while (en.hasMoreElements()) {
      i++;
      s = new String(s+"\n"+i+". "+(Hrana)en.nextElement());
    }
    return s;
  }
}

class Hrana extends Object {
  double a,b,c;
  double dx,dy;
  Bod bod1,bod2;
  Pbod pbod1,pbod2; 

  public Hrana(Hashtable t,Bod bod1,Bod bod2) {
    this.bod1 = bod1;
    this.bod2 = bod2;
    a = bod1.x-bod2.x;
    b = bod1.y-bod2.y;
    double stredx = (bod1.x+bod2.x)/2;
    double stredy = (bod1.y+bod2.y)/2;
    c = -a*stredx - b*stredy;
    pbod1 = pbod2 = null;
    bod1.hrany.put(bod2,this);
    bod2.hrany.put(bod1,this);
    t.put(new Integer(this.hashCode()),this);

    dx = -b; dy = a;
    double lomeno = Math.sqrt(dx*dx+dy*dy);
    dx = dx/lomeno; dy = dy/lomeno;
  }

  public void paint(Graphics g) {
    double x,y,x1,y1,x2,y2;
    x1 = x2 = y1 = y2 = 0.0;
    if (pbod2!=null) {
      x1 = pbod1.x; x2 = pbod2.x; y1 = pbod1.y; y2 = pbod2.y;
    } else {
      if (pbod1!=null) {
        x1 = pbod1.x; y1 = pbod1.y;
        x2 = pbod1.x+Voron.max*dx; 
        y2 = pbod1.y+Voron.max*dy;
      } else {
        x = (bod1.x+bod2.x)/2.0;
        y = (bod1.y+bod2.y)/2.0; 
        x1 = x+Voron.max*dx;
        y1 = y+Voron.max*dy;
        x2 = x-Voron.max*dx;
        y2 = y-Voron.max*dy;
      }
    }
    g.drawLine((int)x1,(int)y1,(int)x2,(int)y2);
  }    

  public void smer(Pbod p1, Pbod p2) {
    dx = pbod2.x-pbod1.x;
    dy = pbod2.y-pbod1.y;
    double lomeno = Math.sqrt(dx*dx+dy*dy);
    dx = dx/lomeno;
    dy = dy/lomeno;
  }

  public void upravHranu(Pbod newPbod, Bod neblizky, Bod blizky) {
    if (pbod2!=null) {
      //System.out.println("Tady2");
      if (pbod2.vzdalenost(neblizky)<pbod2.vzdalenost(blizky)) {
        pbod2.delete(this);
        pbod2 = newPbod;
      }
    }
    if (pbod1!=null) {
      //System.out.println("Tady1");
      if (pbod1.vzdalenost(neblizky)<pbod1.vzdalenost(blizky)) {
        pbod1.delete(this);
        pbod1 = newPbod;
      } else if (pbod2==null) pbod2 = newPbod;
    }
    if ((pbod1==null)&&(pbod2==null)) {
      //System.out.println("Tady");
      pbod1 = newPbod; 
      Bod b = new Bod(pbod1.x+dx,pbod1.y+dy);
      if (b.vzdalenost(neblizky)<b.vzdalenost(blizky)) {
        dx = -dx; dy = -dy;
      }
    }
  }

  public void delete() {
    Pbod p;
    Voron.hrany.remove(new Integer(this.hashCode()));
    bod1.hrany.remove(bod2);
    bod2.hrany.remove(bod1); 
    if ((pbod1==null)&&(pbod2==null)) return;
    if (pbod1!=null) {p=pbod1;pbod1=null;p.delete();}
    if (pbod2!=null) {p=pbod2;pbod2=null;p.delete();}
    //System.out.println("Zrusena hrana "+(Hrana)Voron.hrany.remove(new Integer(this.hashCode())));
  } 

  public String toString() {
    return new String("a: "+a+", b: "+b+", c: "+c+
                       ",bod1: "+bod1+",bod2: "+bod2);
  }
}
    

class Voronoi {
  static Bod oldHost,prvni,novy,stary,host,host1,host2,kolizHost;
  static Pbod newPbod,newPbod1,newPbod2,kolizPbod;
  static Hrana zasazenaHrana,zasazenaHrana1,zasazenaHrana2,
               kolizZasazenaHrana,oldKolizHrana;
  static Pbod pLast,pLevy,pPravy;
  static Bod levy,pravy;
  static Hrana levaHrana,pravaHrana,staticKolizHrana;

  public static void zahajeni() {
    boolean prvni = true;
    Pbod p;

    oldHost=host=host1=host2=kolizHost=null; 
    newPbod=newPbod1=newPbod2=kolizPbod=null;
    zasazenaHrana=zasazenaHrana1=zasazenaHrana2=null;
    kolizZasazenaHrana=oldKolizHrana=null;

    Hrana kolizHrana = oldKolizHrana = new Hrana(Voron.hrany,novy,stary);
    Enumeration en = stary.hrany.elements();
    while(en.hasMoreElements()) {
      Hrana h = (Hrana)en.nextElement();
      if ((p=protni(kolizHrana,h))!=null) {
        if (prvni) {
          zasazenaHrana1 = h;
          //System.out.println("hr1: "+h);
          host1 = (stary==h.bod1)?h.bod2:h.bod1;
          kolizHrana.upravHranu(p,host1,novy);
          newPbod1 = p;
          prvni = false;
        } else if (p!=newPbod1) {
          //System.out.println("hr2: "+h);
          kolizHrana.pbod2 = p;
          zasazenaHrana2 = h;
          host2 = (stary==h.bod1)?h.bod2:h.bod1;
          newPbod2 = p;
        }
      }
    }
  }

  public static boolean kroky() {
    Hrana kolizHrana=null;
    for (;;) {
      //System.out.println("kroky");
      if (kolizHrana!=null) kolizHrana.upravHranu(newPbod,host,oldHost);
      zasazenaHrana.upravHranu(newPbod,novy,oldHost);
      kolizHrana = new Hrana(Voron.hrany,novy,host);
      kolizHrana.upravHranu(newPbod,oldHost,host);
      newPbod.add(kolizHrana);
      if (!koliduj(kolizHrana,host,zasazenaHrana)) return false;
      oldHost = host;
      host = kolizHost;
      newPbod = kolizPbod;
      zasazenaHrana = kolizZasazenaHrana;
      if (zasazenaHrana == zasazenaHrana2) {
        Voron.pbody.remove(new Integer(newPbod.hashCode())); 
        zasazenaHrana.upravHranu(newPbod2,novy,oldHost);
        kolizHrana.upravHranu(newPbod2,host,oldHost);
        newPbod2.add(kolizHrana);
        return true;
      }
    }
  }

  public static void delej(Bod novy) {
    Voronoi.novy = novy;
    Bod b=null;
    Enumeration en = Voron.body.elements();
    double min = Double.POSITIVE_INFINITY;

    while (en.hasMoreElements()) {
      Bod bod = (Bod)en.nextElement();
      double dx = novy.x - bod.x;
      double dy = novy.y - bod.y;
      if ((bod!=novy)&&(min>=(dx*dx+dy*dy))) {
        min=dx*dx+dy*dy;b=bod;
      }
    }
    if (b==null) return;
    if (min==0.0) {Voron.body.remove(new Integer(novy.hashCode())); return;}
    stary = b;
    zahajeni();
    oldHost = stary;
    newPbod = newPbod1;
    host = host1;
    zasazenaHrana = zasazenaHrana1;
    if ((zasazenaHrana!=null)&&!kroky()) {
      //System.out.println("Pokracuj");
      oldHost = stary;
      newPbod = newPbod2;
      host = host2;
      zasazenaHrana = zasazenaHrana2;
      if (zasazenaHrana!=null) kroky();
    }
    zrusPbody();
  }
 

  public static void likviduj(Bod novy) {
    Bod b=null;
    Enumeration en = Voron.body.elements();
    double min = Double.POSITIVE_INFINITY;
    double max = Double.NEGATIVE_INFINITY;

    while (en.hasMoreElements()) {
      Bod bod = (Bod)en.nextElement();
      double dx = novy.x - bod.x;
      double dy = novy.y - bod.y;
      if ((bod!=novy)&&(min>=(dx*dx+dy*dy))) {
        min=dx*dx+dy*dy;b=bod;
      }
    }
    if (b==null) return;
    stary = b;
    b = null;
    en = stary.hrany.keys();
    while (en.hasMoreElements()) {
      Bod bod = (Bod)en.nextElement();
      double dx = stary.x - bod.x;
      double dy = stary.y - bod.y;
      double velikost = Math.sqrt(dx*dx+dy*dy);
      Hrana hrana = (Hrana)stary.hrany.get(bod);
      if (hrana.pbod2==null) velikost = 0;
      else velikost = velikost/hrana.pbod1.vzdalenost(hrana.pbod2);
      if (max<=velikost) {
        max=dx*dx+dy*dy;b=bod;
      }
    }
    if (b==null) {Voron.body.remove(new Integer(stary.hashCode()));return;}
    prvni = b;
    if (likvidZahajeni()) likvidKroky();
    zrusPbody();
  }

  public static boolean likvidZahajeni() {
    Hrana h = (Hrana)stary.hrany.get(prvni);
    if (h.pbod1==null) {
      h.delete();
      Voron.body.remove(new Integer(stary.hashCode()));
      return false;
    } else if (h.pbod2==null) {
      Enumeration en = stary.hrany.keys();
      Bod jeden=null;
      while (en.hasMoreElements()) {
        Bod b = (Bod)en.nextElement();
        if (jeden==null) jeden = b;
        else {
          Hrana g = (Hrana)jeden.hrany.get(b);
          if (g.pbod2==null) {
            g.pbod1.delete(g); 
            g.pbod1=null;
          } else {
            if (g.pbod1.vzdalenost(stary)>g.pbod2.vzdalenost(stary)) {
              g.smer(g.pbod2,g.pbod1);
              g.pbod2.delete(g);
              g.pbod2=null;
            } else {
              g.smer(g.pbod1,g.pbod2);
              g.pbod1.delete(g);
              g.pbod1=g.pbod2;
              g.pbod2=null;
            }
          }
        }
      }
      Voron.body.remove(new Integer(stary.hashCode()));
      return false;
    }
    return true;
  }

  public static boolean prvniPrvni(Hrana kolizHrana, Bod prvni, Bod druhy) {
    return true;
  }
 
  public static Hrana nextHrana(Bod bod1, Bod bod2) {
    return null;
  }

  public static void likvidKroky() {
    boolean konec = false;
    Hrana kolizHrana = staticKolizHrana;
    Bod pom;
    for (;;) {
      pLevy = protni(kolizHrana,levaHrana);
      pPravy = protni(kolizHrana,pravaHrana);
      if (prvniPrvni(kolizHrana,levy,pravy)) {
        kolizHrana.pbod2=pLevy;
        levaHrana.upravHranu(pLevy,pravy,levy);
        pLast = pLevy;
        pLevy.add(kolizHrana);
        pLevy.add(levaHrana);
        pom = levy;
        levy = (levaHrana.bod1==levy)?levaHrana.bod2:levaHrana.bod1; 
        levaHrana = nextHrana(pom,levy);
      } else {
        kolizHrana.pbod2=pPravy;
        pravaHrana.upravHranu(pPravy,levy,pravy);
        pLast = pPravy;
        pPravy.add(kolizHrana);
        pPravy.add(pravaHrana);
        pom = pravy;
        pravy = (pravaHrana.bod1==pravy)?pravaHrana.bod2:pravaHrana.bod1; 
        pravaHrana = nextHrana(pom,pravy);
      }
      if ((kolizHrana=(Hrana)pravy.hrany.get(levy))==null) {
        kolizHrana = new Hrana(Voron.hrany,levy,pravy);
        konec = true;
      }
      pLast.add(kolizHrana);
      kolizHrana.upravHranu(pLast,pom,levy);
      if (konec) return;
    } 
  }  

  public static void zrusPbody() {
    Enumeration en = Voron.pbodToDelete.elements();
    while (en.hasMoreElements()) {
      Pbod p = (Pbod)en.nextElement();
      p.delete();
    }
    Voron.pbodToDelete.clear();
  }
 
  public static boolean koliduj(Hrana kolizHrana, Bod host,
                                Hrana uzZasazena) {
    Hrana h=null;
    Pbod p=null;
    boolean ok = false;
    Enumeration en = host.hrany.elements();
    
    while (en.hasMoreElements()) {
      h = (Hrana)en.nextElement();
      if (h==uzZasazena) continue;
      p = protni(kolizHrana,h);
      if ((p!=null)&&(p!=kolizHrana.pbod1)) {ok = true;break;}
    }
    if (ok) {
      if (h.bod1==host) kolizHost=h.bod2;
      else kolizHost = h.bod1;
      kolizPbod = p;
      kolizZasazenaHrana = h;
      return true;
    }
    return false;
  }

  // zatim jeste neni zabudovan mechanizmus protnuti jineho pbodu
  public static Pbod protni(Hrana kolizHrana, Hrana hrana) {
    Pbod p;
    double dx,dy;

    double a1 = kolizHrana.a;
    double b1 = kolizHrana.b;
    double c1 = kolizHrana.c;
    double a2 = hrana.a;
    double b2 = hrana.b;
    double c2 = hrana.c;
    double lomeno = a1*b2 - a2*b1; 
    if (lomeno == 0) return null;
    double x =  (b1*c2-b2*c1)/lomeno;
    double y = -(a1*c2-a2*c1)/lomeno;
    if (hrana.pbod1!=null) {
      if (hrana.pbod2!=null) {
        dx = Math.abs(hrana.pbod1.x-hrana.pbod2.x);
        dy = Math.abs(hrana.pbod1.y-hrana.pbod2.y);
        if (Math.abs(hrana.pbod1.x-x)>dx) return null; 
        if (Math.abs(hrana.pbod2.x-x)>dx) return null;
        if (Math.abs(hrana.pbod1.y-y)>dy) return null;
        if (Math.abs(hrana.pbod2.y-y)>dy) return null;
      } else {
        if (hrana.dx>0.0) {
          if (hrana.pbod1.x>x) return null;
        } else if (hrana.dx<0.0) {
          if (hrana.pbod1.x<x) return null;
        } else if (hrana.dy>0.0) {
          if (hrana.pbod1.y>y) return null;
        } else if (hrana.dy<0.0) {
          if (hrana.pbod1.y<y) return null;
        }
      }
    }
    p = new Pbod(Voron.pbody,x,y);
    p.add(kolizHrana);
    p.add(hrana);
    return p;
  }
}

class Kresli extends Panel {
  public void paint(Graphics g) {
    //g.clearRect(0,0,10000,10000);
    Enumeration en = Voron.body.elements();
    while (en.hasMoreElements()) {
      Bod b = (Bod)en.nextElement();
      b.paint(g);
    }
    en = Voron.hrany.elements();
    while (en.hasMoreElements()) {
      Hrana h = (Hrana)en.nextElement();
      if (Voron.delay.getState())
        g.drawLine((int)h.bod1.x,(int)h.bod1.y,(int)h.bod2.x,(int)h.bod2.y);
      else h.paint(g);
    }
  }
}
  
     
public class Voron extends Applet {
  static Hashtable body = new Hashtable();
  static Hashtable hrany = new Hashtable();
  static Hashtable pbody = new Hashtable();
  static Hashtable pbodToDelete = new Hashtable();
  final static double max=10000.0;
  Bod pick = null;
  Kresli panel;
  static Checkbox delay;

  public void init() {
    setLayout(new BorderLayout());
    Panel p = new Panel();
    p.add(delay = new Checkbox("Delayova triangulace"));
    p.add(new Button("Start"));
    add("South",p);
    add("Center",panel=new Kresli());
  }

  public void update(Graphics g) {
    panel.repaint();
  }
    
/*
    g = panel.getGraphics();
    g.clearRect(0,0,10000,10000);
    Enumeration en = body.elements();  
    while (en.hasMoreElements()) {
      Bod b = (Bod)en.nextElement();
      b.paint(g);
    }
    en = hrany.elements();
    while (en.hasMoreElements()) {
      Hrana h = (Hrana)en.nextElement();
      if (delay.getState()) 
        g.drawLine((int)h.bod1.x,(int)h.bod1.y,(int)h.bod2.x,(int)h.bod2.y); 
      else h.paint(g);
    }
  }

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

  public boolean mouseDown(Event e, int x, int y) {
    Bod b = null, bod = null;
    Graphics g = getGraphics();
    if (e.modifiers==Event.ALT_MASK) {
      b = new Bod(body,x,y);
      b.paint(g);
      Voronoi.delej(b);
      panel.repaint();
/*
      Enumeration en = body.elements();
      while (en.hasMoreElements()) {
        Bod p = (Bod)en.nextElement();
        System.out.println(p.toText());
      }
    } else if (e.modifiers==Event.META_MASK) {
      b = new Bod(x,y);
      Voronoi.likviduj(b);
      repaint();
*/
    } else {
      System.out.println(x+" "+y);
      repaint();
    }
/*
    } else {
      Enumeration en = body.elements();  
      double min = Double.POSITIVE_INFINITY;
      while (en.hasMoreElements()) {
        bod = (Bod)en.nextElement();
        double dx = (double)x - bod.x;
        double dy = (double)y - bod.y;
        if (min>=(dx*dx+dy*dy)) {min=dx*dx+dy*dy;b=bod;}
      }
      if (b==null) return true;
      Rectangle oldRect=new Rectangle((int)b.x-3,(int)b.y-3,6,6);
      Rectangle newRect=new Rectangle(x-3,y-3,6,6);
      Rectangle r = newRect.union(oldRect); 
      b.x = x; b.y = y;
      g.clearRect(r.x,r.y,r.width,r.height);
      g.clipRect(r.x,r.y,r.width,r.height);
      paint(g); 
    }
*/
    pick = b;
    return true;
  }

  public boolean mouseDrag(Event e, int x, int y) {
/*
    if (pick!=null) {
      Rectangle oldRect=new Rectangle((int)pick.x-3,(int)pick.y-3,6,6);
      Rectangle newRect=new Rectangle(x-3,y-3,6,6);
      Rectangle r = newRect.union(oldRect); 
      Graphics g = getGraphics();
      pick.x = (double)x; pick.y = (double)y;
      g.clearRect(r.x,r.y,r.width,r.height);
      g.clipRect(r.x,r.y,r.width,r.height);
      paint(g);
    }
*/
    return true;
  }

  public boolean mouseUp(Event e, int x, int y) {
/*
    if (pick!=null) {
      Rectangle oldRect=new Rectangle((int)pick.x-3,(int)pick.y-3,6,6);
      Rectangle newRect=new Rectangle(x-3,y-3,6,6);
      Rectangle r = newRect.union(oldRect); 
      Graphics g = getGraphics();
      pick.x = (double)x; pick.y = (double)y;
      g.clearRect(r.x,r.y,r.width,r.height);
      g.clipRect(r.x,r.y,r.width,r.height);
      paint(g);
    }
*/
    return true;
  }

  public boolean handleEvent(Event evt) {
        if (evt.id == Event.ACTION_EVENT) {
            if (evt.target instanceof Checkbox) {
               panel.repaint();
            } else if (evt.target instanceof Button) {
               body.clear();
               hrany.clear();
               pbody.clear();
               pbodToDelete.clear();
               repaint();
            }
        }
        return super.handleEvent(evt);
  } 
}