import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
private Champion nearest(Node node, Champion champ, Point2D p) {
    if (node==null) return champ;

    Double dist = node.point.distanceTo(p);
    if (dist < champ.distance) {
        champ.distance = dist;
        champ.point = node.point;
    }

    int cmp = node.compare(p);
    if (cmp < 0) {
        champ = nearest(node.left, champ, p);
        if (node.verticalDist(p) < champ.distance) {
            champ = nearest(node.right, champ, p);
        }
    }
    else if (cmp > 0) {
        champ = nearest(node.right, champ, p);
        if (node.verticalDist(p) < champ.distance) { champ = nearest(node.left, champ, p); }
    }
    return champ;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public Point2D nearest(Point2D p) {
    if(p == null)
        throw new java.lang.NullPointerException("NULL ARGUMENT!");
    if(isEmpty())
        return null;
    Point2D ptmp = new Point2D(0,0);
    double minD =  Double.POSITIVE_INFINITY;
    for(Point2D ptable : rbst.keys()) {
        double tmpD = p.distanceSquaredTo(ptable);
        if(tmpD < minD) {
            minD = tmpD;
            ptmp = ptable;
        }
    }
    return ptmp;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
private int countTriples(Point2D[] points) {

        boolean allYCoordinatesAreXCubic = true;

        for(Point2D point2D : points) {

            if (point2D.y() != Math.pow(point2D.x(), 3)) {
                allYCoordinatesAreXCubic = false;
                break;
            }
        }

        if (allYCoordinatesAreXCubic) {
            return countTriplesWithCubicYs(points);
        } else {
            return countTriplesUsingSlopes(points);
        }
    }
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
private static void drawAndCreatePoints(Point2D[] points) {
	
	StdDraw.setCanvasSize(1024, 512);
	StdDraw.setPenRadius(.015);
       StdDraw.setXscale(0, 1);
       StdDraw.setYscale(0, 1);
	
	for (int i = 0; i<points.length; i++) {

		double pointX = StdRandom.uniform();
		double pointY = StdRandom.uniform();
		
		Point2D point = new Point2D(pointX, pointY);
		StdDraw.point(point.x(), point.y()); //The exercise doesn't require drawing, but it adds a nice touch
		
		points[i] = point;
	}
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
private static double calculateShortestDistance(Point2D[] points) {
	
	double shortestDistance = Double.MAX_VALUE;
	double currentDistance = Double.MAX_VALUE;
	
	Arrays.sort(points, points[0].distanceToOrder());
	
	for (int i = 1; i < points.length; i++) {
		currentDistance = points[i].distanceTo(points[i-1]);
		
		if (currentDistance < shortestDistance) {
			shortestDistance = currentDistance;
		}
	}
	
	return shortestDistance;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public static void main(String[] args) {
    RectHV rect = new RectHV(0.0, 0.0, 1.0, 1.0);
    StdDraw.show(0);
    KdTree kdtree = new KdTree();
    while (true) {
        if (StdDraw.mousePressed()) {
            double x = StdDraw.mouseX();
            double y = StdDraw.mouseY();
            StdOut.printf("%8.6f %8.6f\n", x, y);
            Point2D p = new Point2D(x, y);
            if (rect.contains(p)) {
                StdOut.printf("%8.6f %8.6f\n", x, y);
                kdtree.insert(p);
                StdDraw.clear();
                kdtree.draw();
            }
        }
        StdDraw.show(50);
    }

}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public Point2D nearest(Point2D target)
{
	assertArgument(target);

	Point2D champion = null;

	double best = Double.POSITIVE_INFINITY;

	for (Point2D point : set)
	{
		double distance = point.distanceTo(target);

		if (champion == null || distance < best)
		{
			champion = point;
			best = distance;
		}
	}

	return champion;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
private int compare(Point2D p) {
    if (point.compareTo(p)==0) { return 0; }

    if (vertical) {
        if      (p.x() < point.x()) { return -1; }
        else if (p.x() > point.x()) { return  1; }
        else                        { return -1; }
    }
    else {
        if      (p.y() < point.y()) { return -1; }
        else if (p.y() > point.y()) { return  1; }
        else                        { return -1; }
    }
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
private Node insert(Node node, Point2D p, boolean vertical) {
    if (node==null) {
        this.N++;
        return new Node(p, vertical);
    }

    assert (node.vertical == vertical);
    int cmp = node.compare(p);
    if      (cmp < 0) { node.left  = insert(node.left,  p, !vertical); }
    else if (cmp > 0) { node.right = insert(node.right, p, !vertical); }

    return node;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public boolean contains(Point2D p) {
    Node node = root;

    while (node!=null) {
        int cmp = node.compare(p);
        if      (cmp < 0) { node = node.left;  }
        else if (cmp > 0) { node = node.right; }
        else              { return true;       }
    }

    return false;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
private void range(ArrayList<Point2D> list, Node node, RectHV rect) {
    if (node==null) return;

    int cmp = node.compare(rect);

    if      (cmp > 0) { range(list, node.right, rect); }
    else if (cmp < 0) { range(list, node.left,  rect); }
    else {
        if (rect.contains(node.point)) { list.add(node.point); }
        range(list, node.left, rect);
        range(list, node.right, rect);
    }
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public Iterable<Point2D> range(RectHV rect) {
    if (rect==null) { throw new IllegalArgumentException(); }

    ArrayList<Point2D> it = new ArrayList<>();
    for (Point2D p: set) { if (rect.contains(p)) { it.add(p); } }
    return it;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public Vector updatePositionAndVelocity(Boid nearest) {
    double x = x() + velocity.cartesian(0);
    double y = y() + velocity.cartesian(1);
    position = new Point2D(x, y);
    Vector desire = eatBoid(nearest).direction().scale(0.0003);
    velocity = velocity.plus(desire);
    return desire;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
private static Iterable<Boid> lookUpBoids(KdTreeST<Boid> bkd, Iterable<Point2D> points) {
    Queue<Boid> values = new Queue<Boid>();
    for (Point2D p : points) {
        values.enqueue(bkd.get(p));
    }
    return values;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public Iterable<Point2D> range(RectHV rect) {
    if(rect == null)
        throw new java.lang.NullPointerException("NULL ARGUMENT!");
    Queue<Point2D> internalPoints = new Queue<>();
    for(Point2D p : rbst.keys())
        if(rect.contains(p))
            internalPoints.enqueue(p);
    return internalPoints;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public Vector updatePositionAndVelocity(Iterable<Boid> neighbors, Hawk hawk) {
    double x = x() + velocity.cartesian(0);
    double y = y() + velocity.cartesian(1);
    position = new Point2D(x, y);
    Vector desire = desiredAcceleration(neighbors, hawk);
    velocity = velocity.plus(desire);
    return desire;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public static void main(String[] args) {

        Exercise26_3Collinearity exercise26_3Collinearity = new Exercise26_3Collinearity();

        Point2D[] points = new Point2D[6];
        for(int i = 0; i < points.length; i++) {
            Point2D point = new Point2D(i, i + 1.5);
            points[i] = point;
        }

        int numberOfTriples1 = exercise26_3Collinearity.countTriples(points);
        StdOut.println("Number of triples: " + numberOfTriples1  + " Expected: 10");

        //Based on https://www.algebra.com/algebra/homework/Length-and-distance/Length-and-distance.faq.question.530663.html
        //(-3,4) (3,2) (6,1) are on the same line
        Point2D pointA = new Point2D(-3, 4);
        Point2D pointB = new Point2D(3, 2);
        Point2D pointC = new Point2D(6, 1);

        Point2D[] points2 = {pointA, pointB, pointC};

        int numberOfTriples2 = exercise26_3Collinearity.countTriples(points2);
        StdOut.println("Number of triples: " + numberOfTriples2  + " Expected: 1");

        Point2D pointD = new Point2D(6, 1);

        Point2D[] points3 = {pointA, pointB, pointC, pointD};

        int numberOfTriples3 = exercise26_3Collinearity.countTriples(points3);
        StdOut.println("Number of triples: " + numberOfTriples3  + " Expected: 3");

        //Case with cubic y coordinate
        Point2D pointE = new Point2D(1, 1);
        Point2D pointF = new Point2D(2, 8);
        Point2D pointG = new Point2D(-3, -27);

        Point2D[] points4 = {pointE, pointF, pointG};
        int numberOfTriples4 = exercise26_3Collinearity.countTriples(points4);
        StdOut.println("Number of triples: " + numberOfTriples4  + " Expected: 1");
    }
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public Iterable<Point2D> range(RectHV rect)
{
	assertArgument(rect);

	ArrayList<Point2D> points = new ArrayList<>(set.size());

	for (Point2D point : set)
	{
		if (rect.contains(point)) points.add(point);
	}

	return points;
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
public static void main(String[] args)
{
	PointSET set = new PointSET();

	set.insert(new Point2D(1, 1));
	set.insert(new Point2D(2, 2));
	set.insert(new Point2D(3, 3));

	System.out.println(set.nearest(new Point2D(1.5, 1.5)).toString());
}
 

import edu.princeton.cs.algs4.Point2D; //导入依赖的package包/类
private Node(Point2D p, boolean vertical) {
    point = p;
    this.vertical = vertical;
}