Programming Assignment 3: Collinear Points
15784 단어 programming
Point data type. Create an immutable data type Point that represents a point in the plane by implementing the following API:
public class Point implements Comparable
To get started, use the data type Point.java , which implements the constructor and the draw(), drawTo(), and toString() methods. Your job is to add the following components.
import java.util.Comparator;
public class Point implements Comparable<Point> {
public final Comparator<Point> SLOPE_ORDER = new PointCmp();
private final int x; // x coordinate
private final int y; // y coordinate
public Point(int x, int y) {
/* DO NOT MODIFY */
this.x = x;
this.y = y;
}
public void draw() {
/* DO NOT MODIFY */
StdDraw.point(x, y);
}
public void drawTo(Point that) {
/* DO NOT MODIFY */
StdDraw.line(this.x, this.y, that.x, that.y);
}
public double slopeTo(Point that) {
/* YOUR CODE HERE */
if (this.compareTo(that) == 0)
return Double.POSITIVE_INFINITY*-1;
else if (this.x == that.x)
return Double.POSITIVE_INFINITY;
else if (this.y == that.y)
return +0;
else
return (that.y - this.y) * 1.0 / (that.x - this.x);
}
private class PointCmp implements Comparator<Point> {
@Override
public int compare(Point o1, Point o2) {
// TODO Auto-generated method stub
if (slopeTo(o1) < slopeTo(o2) || (slopeTo(o1) == slopeTo(o2) && o1.compareTo(o2) == -1))
return -1;
else if (slopeTo(o1) > slopeTo(o2) || (slopeTo(o1) == slopeTo(o2) && o1.compareTo(o2) == 1))
return 1;
else
return 0;
}
}
@Override
public int compareTo(Point that) {
// TODO Auto-generated method stub
if (this.y < that.y || (this.y == that.y && this.x < that.x))
return -1;
else if (this.y == that.y && this.x == that.x)
return 0;
else
return 1;
}
public String toString() {
/* DO NOT MODIFY */
return "(" + x + ", " + y + ")";
}
public static void main(String[] args) {
// TODO Auto-generated method stub
In in = new In(args[0]);
int num = in.readInt();
Point points[] = new Point[num];
for (int i = 0; i < num; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
}
}
}
Brute force. Write a program Brute.java that examines 4 points at a time and checks whether they all lie on the same line segment, printing out any such line segments to standard output and drawing them using standard drawing. To check whether the 4 points p, q, r, and s are collinear, check whether the slopes between p and q, between p and r, and between p and s are all equal.
The order of growth of the running time of your program should be N4 in the worst case and it should use space proportional to N.
public class Brute {
public static void main(String[] args) {
// rescale coordinates and turn on animation mode
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
StdDraw.show(0);
StdDraw.setPenRadius(0.01); // make the points a bit larger
// read in the input
String filename = args[0];
In in = new In(filename);
int N = in.readInt();
Point points[] = new Point[N];
for (int i = 0; i < N; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
points[i].draw();
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - i - 1; j++) {
if (points[j].compareTo(points[j+1]) == 1) {
Point temp = points[j];
points[j] = points[j + 1];
points[j + 1] = temp;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
for (int k = j + 1; k < N; k++) {
for(int l = k + 1; l < N; l++) {
if(points[i].slopeTo(points[j]) == points[j].slopeTo(points[k])&&
points[j].slopeTo(points[k]) == points[k].slopeTo(points[l])) {
points[i].drawTo(points[l]);
StdOut.print(points[i].toString()+" -> "+points[j].toString()
+" -> "+points[k].toString()+" -> "+points[l].toString());
StdOut.println();
}
}
}
}
}
// display to screen all at once
StdDraw.show(0);
// reset the pen radius
StdDraw.setPenRadius();
}
}
A faster, sorting-based solution. Remarkably, it is possible to solve the problem much faster than the brute-force solution described above. Given a point p, the following method determines whether p participates in a set of 4 or more collinear points.
Applying this method for each of the N points in turn yields an efficient algorithm to the problem. The algorithm solves the problem because points that have equal slopes with respect to p are collinear, and sorting brings such points together. The algorithm is fast because the bottleneck operation is sorting.
Write a program Fast.java that implements this algorithm. The order of growth of the running time of your program should be N2 log N in the worst case and it should use space proportional to N.
소스 코드 보정 대기;