// Given an array of Point objects, and a parameter delta, we can
// construct the WeightedEdgeGraph G containing an edge for each pair of
// points at distance less than delta.  We try to do this faster
// than O(V*V) time, by sorting the points into bags, one bag per
// square of side-length delta.  Then we only have to compare points
// that are in the same square, or in adjacent squares.

import java.util.HashMap;

public class GeomGraph extends EdgeWeightedGraph
{
    // Array of Point objects, given in our constructor.
    final private Point[] points;

    // We add all edges of length less than delta.
    final double delta;

    // A Square (ix,iy) is a square of side delta in the plane.
    // It contains all points (x,y) such that:
    //      ix*delta <= x < (ix+1)*delta  and
    //      iy*delta <= y < (iy+1)*delta
    private class Square
    {
        // These indices identify the Square:
        final int ix, iy;
        // Create a Square.
        Square(int ix, int iy) { this.ix = ix; this.iy = iy; }
        // Create a Square containing Point p.
        Square(Point p) {
            this((int)Math.floor(p.x/delta), (int)Math.floor(p.y/delta));
        }
        // Four neighboring squares:
        Square up()    { return new Square(ix, iy+1); }
        Square down()  { return new Square(ix, iy-1); }
        Square left()  { return new Square(ix-1, iy); }
        Square right() { return new Square(ix+1, iy); }

        // These two methods make Square usable as a HashMap key.
        public int hashCode() { return ix + iy + (iy << 16); }
        public boolean equals(Object o) {
            Square that = (Square)o;
            return this.ix == that.ix && this.iy == that.iy;
        }
    }

    // A counter for the number of pairs tried (not all pairs
    // become edges, because their distance is too large).
    private int pairs = 0;
    public int pairs() { return pairs; }

    // We map each non-empty Square s to a list of ids of the
    // Point objects (in the points[] array) that s contains.
    private HashMap<Square,Bag<Integer>> bags =
        new HashMap<Square,Bag<Integer>>();

    // Add all edges of length less than delta from vertex u
    // to vertices v in the bag of square s.
    private void addEdges(int u, Square s) {
        Bag<Integer> bag = bags.get(s);
        if (bag == null) return;
        Point p = points[u];
        for (int v: bag) {
            Point q = points[v];
            double dist = p.distanceTo(q);
            ++pairs;
            if (dist < delta)
                addEdge(new Edge(u, v, dist));
        }
    }

    // Return a Point from the points[] array.
    public Point point(int v) { return points[v]; }

    public GeomGraph(Point[] points, double delta)
    {
        super(points.length);   // sets V in base EdgeWeightedGraph
        this.delta = delta;
        this.points = points;
        // For each point p, compare it to all points in the same
        // square, and all points in the eight neighboring squares.
        for (int u=0; u<V(); ++u) {
            // u is the id of point p, which is in square s.
            Point p = points[u];
            Square s = new Square(p);
            // Add all possible edges from p of length less than delta.
            addEdges(u, s);
            addEdges(u, s.left());
            addEdges(u, s.right());
            Square up = s.up();
            addEdges(u, up);
            addEdges(u, up.left());
            addEdges(u, up.right());
            Square down = s.down();
            addEdges(u, down);
            addEdges(u, down.left());
            addEdges(u, down.right());
            // Finally add u to the bag of s (create if necessary).
            Bag<Integer> bag = bags.get(s);
            if (bag == null)
                bags.put(s, bag = new Bag<Integer>());
            bag.add(u);
        }
    }
}