import java.awt.*;
import java.util.ArrayList;
import java.util.List;

class QuadTree {
    private static final int CAPACITY = 4;

    private final AABB boundary;

    private List<Node> points = new ArrayList<>();

    private QuadTree northWest;
    private QuadTree northEast;
    private QuadTree southWest;
    private QuadTree southEast;

    QuadTree(AABB boundary){
        this.boundary = boundary;
    }

    Node closestNode(Point clickPoint, Location origin, double scale){
        Location clickLocation = Location.newFromPoint(clickPoint, origin, scale);
        return closestNode(clickLocation);
    }

    private Node closestNode(Location clickLocation){
        if(!boundary.containsPoint(clickLocation)) return null;
        if(northWest != null){
            Node nwClosestNode = northWest.closestNode(clickLocation);
            Node neClosestNode = northEast.closestNode(clickLocation);
            Node seClosestNode = southEast.closestNode(clickLocation);
            Node swClosestNode = southWest.closestNode(clickLocation);
            Node closestNode = null;
            if(nwClosestNode != null) closestNode = nwClosestNode;
            if(neClosestNode != null) closestNode = neClosestNode;
            if(seClosestNode != null) closestNode = seClosestNode;
            if(swClosestNode != null) closestNode = swClosestNode;
            double distance;
            if(closestNode == null) distance = Double.MAX_VALUE;
            else {
                double xdiff = clickLocation.x - closestNode.getLocation().x;
                double ydiff = clickLocation.y - closestNode.getLocation().y;
                distance = (xdiff * xdiff) + (ydiff * ydiff);
            }
            if(nwClosestNode == null) closestNode = closerNode(clickLocation, closestNode, distance);
            if(neClosestNode == null) closestNode = closerNode(clickLocation, closestNode, distance);
            if(seClosestNode == null) closestNode = closerNode(clickLocation, closestNode, distance);
            if(swClosestNode == null) closestNode = closerNode(clickLocation, closestNode, distance);
            return closestNode;
        }
        Node closestNode = closestPointInQuad(clickLocation);
        return closestNode;
    }

    private Node closerNode(Location clickLocation, Node closestNode, double distance){
        if(!(boundary.containsPoint(new Location(clickLocation.x + distance, clickLocation.y)) ||
                boundary.containsPoint(new Location(clickLocation.x - distance, clickLocation.y)) ||
                boundary.containsPoint(new Location(clickLocation.x, clickLocation.y + distance)) ||
                boundary.containsPoint(new Location(clickLocation.x, clickLocation.y - distance)))){
            return closestNode;
        }
        if(northWest != null){
            Node nwClosestNode = northWest.closerNode(clickLocation, closestNode, distance);
            Node neClosestNode = northEast.closerNode(clickLocation, closestNode, distance);
            Node seClosestNode = southEast.closerNode(clickLocation, closestNode, distance);
            Node swClosestNode = southWest.closerNode(clickLocation, closestNode, distance);
            if(nwClosestNode != null) return nwClosestNode;
            if(neClosestNode != null) return neClosestNode;
            if(seClosestNode != null) return seClosestNode;
            if(swClosestNode != null) return swClosestNode;
        }
        closestNode = closestNodeInQuad(clickLocation, closestNode, distance);
        return closestNode;
    }

    private Node closestPointInQuad(Location clickLocation){
        return closestNodeInQuad(clickLocation, null, Double.MAX_VALUE);
    }

    private Node closestNodeInQuad(Location clickLocation, Node closestNode, double lowestDistance){
        for(Node n : points){
            double xdiff = clickLocation.x - n.getLocation().x;
            double ydiff = clickLocation.y - n.getLocation().y;
            double distance = (xdiff*xdiff) + (ydiff*ydiff);
            if(distance < lowestDistance){
                lowestDistance = distance;
                closestNode = n;
            }
        }
        return closestNode;
    }

    boolean insert(Node n){
        if(!boundary.containsPoint(n.getLocation()))
            return false;

        if(points.size() < CAPACITY){
            points.add(n);
            return true;
        }

        if(northWest == null)
            subdivide();

        if(northWest.insert(n)) return true;
        if(northEast.insert(n)) return true;
        if(southWest.insert(n)) return true;
        if(southEast.insert(n)) return true;

        return false;
    }

    private void subdivide(){
        northWest = new QuadTree(new AABB(new Location(boundary.getCentre().x - boundary.getHalfDimension()/2,
                                                       boundary.getCentre().y - boundary.getHalfDimension()/2),
                                          boundary.getHalfDimension()/2));
        northEast = new QuadTree(new AABB(new Location(boundary.getCentre().x + boundary.getHalfDimension()/2,
                                                       boundary.getCentre().y - boundary.getHalfDimension()/2),
                                          boundary.getHalfDimension()/2));
        southWest = new QuadTree(new AABB(new Location(boundary.getCentre().x - boundary.getHalfDimension()/2,
                                                       boundary.getCentre().y + boundary.getHalfDimension()/2),
                                          boundary.getHalfDimension()/2));
        southEast = new QuadTree(new AABB(new Location(boundary.getCentre().x + boundary.getHalfDimension()/2,
                                                       boundary.getCentre().y + boundary.getHalfDimension()/2),
                                          boundary.getHalfDimension()/2));

        for(Node n : points){
            northWest.insert(n);
            northEast.insert(n);
            southWest.insert(n);
            southEast.insert(n);
        }
    }

    void draw(Graphics g, Location location, double scale){
        if(boundary != null) boundary.draw(g, location, scale);
        if(northEast != null) northEast.draw(g, location, scale);
        if(northWest != null) northWest.draw(g, location, scale);
        if(southEast != null) southEast.draw(g, location, scale);
        if(southWest != null) southWest.draw(g, location, scale);
        for(Node n : points) n.draw(g, location, scale);
    }


}

class AABB {
    private final Location centre;
    private final double halfDimension;

    AABB(Location centre, double halfDimension){
        this.centre = centre;
        this.halfDimension = halfDimension;
    }

    boolean containsPoint(Location l){
        if(l.x < centre.x + halfDimension && l.x > centre.x - halfDimension){
            if(l.y < centre.y + halfDimension && l.y > centre.y - halfDimension){
                return true;
            }
        }
        return false;
    }

    void draw(Graphics g, Location location, double scale){
        Location nw = new Location(centre.x - halfDimension, centre.y + halfDimension);
        Location se = new Location(centre.x + halfDimension, centre.y - halfDimension);
        Point nwPoint = nw.asPoint(location, scale);
        Point sePoint = se.asPoint(location, scale);
        g.drawRect(nwPoint.x, nwPoint.y, Math.abs(sePoint.x - nwPoint.x),Math.abs( sePoint.y - nwPoint.y));
    }

    Location getCentre() {
        return centre;
    }

    double getHalfDimension() {
        return halfDimension;
    }
}