1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
/*************************************************************************
* Name:
* Email:
*
* Compilation: javac Point.java
* Execution:
* Dependencies: StdDraw.java
*
* Description: An immutable data type for points in the plane.
*
*************************************************************************/
import java.util.Comparator;
public class Point implements Comparable<Point> {
// compare points by slope
public final Comparator<Point> SLOPE_ORDER = new SlopeOrder();
private final int x; // x coordinate
private final int y; // y coordinate
// create the point (x, y)
public Point(int x, int y) {
/* DO NOT MODIFY */
this.x = x;
this.y = y;
}
// plot this point to standard drawing
public void draw() {
/* DO NOT MODIFY */
StdDraw.point(x, y);
}
// draw line between this point and that point to standard drawing
public void drawTo(Point that) {
/* DO NOT MODIFY */
StdDraw.line(this.x, this.y, that.x, that.y);
}
// slope between this point and that point
public double slopeTo(Point that) {
if (this.y == that.y && this.x == that.x) return Double.NEGATIVE_INFINITY;
double dx = that.x - this.x;
if (dx == 0.0) return Double.POSITIVE_INFINITY;
double dy = that.y - this.y;
if (dy == 0.0) return +0;
return dy / dx;
}
private class SlopeOrder implements Comparator<Point>
{
public int compare(Point p, Point q)
{
double sp = slopeTo(p);
double sq = slopeTo(q);
if (sp < sq) return -1;
if (sp > sq) return 1;
return 0;
}
}
// is this point lexicographically smaller than that one?
// comparing y-coordinates and breaking ties by x-coordinates
public int compareTo(Point that) {
if (this.y < that.y) return -1;
if (this.y > that.y) return 1;
if (this.x < that.x) return -1;
if (this.x > that.x) return 1;
return 0;
}
// return string representation of this point
public String toString() {
/* DO NOT MODIFY */
return "(" + x + ", " + y + ")";
}
// unit test
public static void main(String[] args) {
System.out.println("Point.java asserts");
Point p0 = new Point(5, 4);
Point p1 = new Point(5, 4);
Point p2 = new Point(9, 3);
Point p3 = new Point(0, 5);
Point p4 = new Point(4, 4);
Point p5 = new Point(6, 4);
assert (p0.compareTo(p1) == 0) : "compareTo p1";
assert (p0.compareTo(p2) == 1) : "compareTo p2";
assert (p0.compareTo(p3) == -1) : "compareTo p3";
assert (p0.compareTo(p4) == 1) : "compareTo p4";
assert (p0.compareTo(p5) == -1) : "compareTo p5";
Point[] pts = new Point[8];
pts[0] = new Point(-5, 3);
pts[1] = new Point(3, 5);
pts[2] = new Point(4, 3);
pts[3] = new Point(3, 3);
pts[4] = new Point(3, 0);
pts[5] = new Point(9, 6);
pts[6] = new Point(5, 5);
pts[7] = new Point(6, 0);
Point ref = pts[3];
System.out.println("REF: "+ref);
Selection.sort(pts, ref.SLOPE_ORDER);
double t = Double.NEGATIVE_INFINITY;
for (Point p : pts)
{
assert t <= ref.slopeTo(p);
System.out.println(" "+p+" "+ref.slopeTo(p));
t = ref.slopeTo(p);
}
System.out.println("SUCCESS");
}
}
|
