
import java.io.*;

import java.util.Hashtable;

public class Beck1 {

   Hashtable array = new Hashtable(10000, 0.70f);

  public void insert(point p) {
    long key;
    Long Key;
    key = (long) p.x;
    Key = new Long( (key /10)*10  );
    array.put(Key,p);
  }

  public void init() {
      // 0.7   wenn 71% besetzt dann neuordnen
    Hashtable array = new Hashtable(100, 0.70f);
    // Einfügen der Daten
    insert( new point(19.0, 21.00) );
    insert( new point(21.0, 24.00) );
    insert( new point(23.0, 24.00) );
    insert( new point(25.0, 23.00) );
    insert( new point(26.0, 24.00) );
    insert( new point(17.0, 18.00) );
  }

  public double distanz(point p1, point p2) {
    double d1, d2;
    d1 = p1.x - p2.x;
    d2 = p1.y - p2.y;
    return Math.sqrt(d1*d1 + d2*d2);
  }

  public point getPoint(point p) {
    long key;
    Long Key1, Key2, Key3;
    double d1, d2, d3;
    point p1, p2, p3;
    point erg;
    key = (long) p.x;
    key = (key /10)*10;
    Key1 = new Long(key);
    Key2 = new Long(key-10);
    Key3 = new Long(key+10);
    p1 =  (point) array.get( Key1 );
    p2 =  (point) array.get( Key2 );
    p3 =  (point) array.get( Key3 );
    // nun mittels Pythagoras die minimale Distanz berechnen
    // Problem:  man darf sich nicht selber finden
    if (p1!=null)
      d1 = distanz(p,p1);
    else
      d1=-1;
    if (p2!=null)
      d2 = distanz(p,p2);
    else
      d2=-1;
    if (p3!=null)
      d3 = distanz(p,p3);
    else
      d3=-1;
    System.out.println("in getPoints");
    System.out.println("p: "+p);
    System.out.println(" p1: "+p1+"\n   p2: "+p2+"\n   p3: "+p3);
    System.out.println(" d1: "+d1+"\n   d2: "+d2+"\n   d3: "+d3);
    erg=p1;
    return erg;
  }

  public void run() {
    point p1, p2;
    long t1, t2;
    t1 =  System.currentTimeMillis();
    // Suchen
    p1 = new point(21.0, 24.00);
    p2 = getPoint(p1);
    System.out.println("p1: "+p1+"\n   p2: "+p2);
    t2 =  System.currentTimeMillis();
    System.out.println("Zeit: "+(t2-t1) );

   // return 21;
  }

	public static void main(String[] args) {
   Beck1 b = new Beck1();
   b.init();
   b.run();
   System.out.println("Habe Fertig");
   pause();

  } // main

   private static void pause() {
    try {
      System.in.read();
    }
    catch (IOException e) {
    }
  }  // pause

}




class point {
  public double x;
  public double y;

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

  public String toString() {
    return "x:  "+x+"    y:  "+y;
  }

}
