001package algs13; 002import stdlib.*; 003import algs12.Point2D; 004/* *********************************************************************** 005 * Compilation: javac Grid.java 006 * Execution: java Grid N d 007 * Dependencies: Queue.java 008 * 009 * Generate N random Euclidean points in unit box (coorinates 010 * between 0 and 1) and print out all pairs that are at 011 * distance <= d. 012 * 013 *************************************************************************/ 014 015public class XGrid { 016 017 public static void main(String[] args) { 018 int N = Integer.parseInt(args[0]); 019 double d = Double.parseDouble(args[1]); 020 021 int G = (int) (Math.ceil(1.0 / d)); // rows and columns in grid 022 023 // initialize data structure 024 @SuppressWarnings("unchecked") 025 final 026 Queue<Point2D>[][] grid = new Queue[G+2][G+2]; 027 for (int i = 0; i <= G+1; i++) 028 for (int j = 0; j <= G+1; j++) 029 grid[i][j] = new Queue<>(); 030 031 // generate random points and check if any previous point <= d 032 for (int n = 0; n < N; n++) { 033 double x = Math.random(); 034 double y = Math.random(); 035 Point2D p = new Point2D(x, y); 036 int row = 1 + (int) (x * G); 037 int col = 1 + (int) (y * G); 038 for (int i = row-1; i <= row+1; i++) { 039 for (int j = col-1; j <= row+1; j++) { 040 for (Point2D q : grid[i][j]) 041 if (p.distanceTo(q) <= d) 042 StdOut.println(p + " <--> " + q); 043 } 044 } 045 grid[row][col].enqueue(p); 046 } 047 } 048} 049