import java.awt.geom.Point2D;

import java.awt.geom.Rectangle2D;

import java.util.ArrayList;

import java.util.List;

public class SplitTree {

private final SplitTreeNode root;

public SplitTree(List points) {

root = buildSplitTree(points, true);

}

// TODO: Finish the implementation of this method. Feel free to modify its arguments.

private SplitTreeNode buildSplitTree(List points, boolean splitX) {

if (points == null || points.isEmpty()) {

return null;

}

// TODO: Find the median point

Point2D p = null;

// TODO: Split the point set the right way

List first = null;

List second = null;

SplitTreeNode node = new SplitTreeNode(p);

node.child1 = buildSplitTree(first, !splitX);

node.child2 = buildSplitTree(second, !splitX);

return node;

}

public int countPointsInRectangle(Rectangle2D rect) {

return countPointsInRectangle(rect, root, true);

}

// TODO: implement

private int countPointsInRectangle(Rectangle2D rect, SplitTreeNode subtree, boolean splitX) {

return 0;

}

private class SplitTreeNode {

Point2D point;

SplitTreeNode child1, child2;

private SplitTreeNode(Point2D point) {

this.point = point;

}

}

public static void main(String[] args) {

// This performs a small test

List points = new ArrayList<>();

points.add(new Point2D.Double(192, 656));

points.add(new Point2D.Double(224, 720));

points.add(new Point2D.Double(320, 688));

SplitTree tree = new SplitTree(points);

System.out.print("Testing basic correctness: ");

if (tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 1000, 1000)) != 3

|| tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 300, 1000)) != 2

|| tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 200, 1000)) != 1

|| tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 1000, 700)) != 2

|| tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 1000, 660)) != 1

|| tree.countPointsInRectangle(new Rectangle2D.Double(0, 0, 1000, 600)) != 0) {

System.out.println("SplitTree counts points incorrectly!");

} else {

System.out.println("Everything seems fine so far.");

}

System.out.println("Testing basic efficiency: this should take less than a second...");

long start = System.currentTimeMillis();

for (int i = 0; i < 10000; i++) {

points.add(new Point2D.Double(1000 * Math.random(), 1000 * Math.random()));

}

tree = new SplitTree(points);

for (int i = 0; i < 100000; i++) {

tree.countPointsInRectangle(new Rectangle2D.Double(1000 * Math.random(), 1000 * Math.random(), 50, 50));

}

System.out.println("Done. That took " + ((System.currentTimeMillis() - start) / 1000.0) + " seconds.");

}

}