``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 ``` ```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[][] 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); } } } ```