package algs13;
import stdlib.*;
import algs12.Point2D;
/* ***********************************************************************
 *  Compilation:  javac Grid.java
 *  Execution:    java Grid N d
 *  Dependencies: Queue.java
 *
 *  Generate N random Euclidean points in unit box (coorinates
 *  between 0 and 1) and print out all pairs that are at
 *  distance <= d.
 *
 *************************************************************************/

public class XGrid {

  public static void main(String[] args) {
    int N    = Integer.parseInt(args[0]);
    double d = Double.parseDouble(args[1]);

    int G = (int) (Math.ceil(1.0 / d));    // rows and columns in grid

    // initialize data structure
    @SuppressWarnings("unchecked")
    final
    Queue<Point2D>[][] grid = new Queue[G+2][G+2];
    for (int i = 0; i <= G+1; i++)
      for (int j = 0; j <= G+1; j++)
        grid[i][j] = new Queue<>();

    // generate random points and check if any previous point <= d
    for (int n = 0; n < N; n++) {
      double x = Math.random();
      double y = Math.random();
      Point2D p  = new Point2D(x, y);
      int row = 1 + (int) (x * G);
      int col = 1 + (int) (y * G);
      for (int i = row-1; i <= row+1; i++) {
        for (int j = col-1; j <= row+1; j++) {
          for (Point2D q : grid[i][j])
            if (p.distanceTo(q) <= d)
              StdOut.println(p + " <--> " + q);
        }
      }
      grid[row][col].enqueue(p);
    }
  }
}