在排序上找到一个斜坡上的点Java

Question

所以我正在做一个任务，我很困难。 安装是这一个http://www.cs.princeton.edu/courses/archive/fall05/cos226/assignments/lines.html 基本上它涉及到写3个类。第一个，point.java用于保存有关XY平面中某个点的信息。 然后，该任务会要求您在同一行上找到每个组合的4个点（具有相同的斜率） 首先，您使用Brute.java执行此操作，比较每种可能的组合，然后使用Fast.jave在那里你选择一个起点并从那里进行比较，然后不要再使用该点。这样你避免检查相同的点。

我卡在的部分是最后一个Fast.java。 我得到几乎正确的输出，除了最后两行被交换的事实。 鉴于输入

15 
10000 0 
8000 2000 
2000 8000 
0 10000 

20000 0 
18000 2000 
2000 18000 

10000 20000 
30000 0 
0 30000 
20000 10000 

13000 0 
11000 3000 
5000 12000 
9000 6000 

我排序前阵我发现斜坡上的点。 数组排序，前调用getLines则是这样的：

(10000, 0) 
(8000, 2000) 
(2000, 8000) 
(0, 10000) 
(20000, 0) 
(18000, 2000) 
(2000, 18000) 
(10000, 20000) 
(30000, 0) 
(0, 30000) 
(20000, 10000) 
(13000, 0) 
(11000, 3000) 
(5000, 12000) 
(9000, 6000) 

这里是我的Point类：

public class Point implements Comparable<Point> { 

public final int x, y; 

// compare points by slope 
public final Comparator<Point> SLOPE_ORDER = new Comparator<Point>() 
     { 
      @Override 
      public int compare(Point arg0, Point arg1) { 
       // TODO Auto-generated method stub 
       if(slopeTo(arg0) < slopeTo(arg1)){ 
        return -1; 
       } 
       if(slopeTo(arg0) > slopeTo(arg1)){ 
        return 1; 
       } 
       else{ 
        return 0; 
       } 
      } 
     }; 

// create the point (x, y) 
public Point(int x, int y) { 
    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) { 
    // TODO: Implement this 

    if(this.x == that.x){ 
     return Double.NEGATIVE_INFINITY; 
    } 
    else if(that.y - this.y == 0){ 
     return 0; 
    } 
    else if(this.x == that.x){ 
     return Double.POSITIVE_INFINITY; 
    } 
    else{ 
     return (((double)that.y - (double)this.y)/((double)that.x - (double)this.x)); 
    } 
} 

/** 
* Is this point lexicographically smaller than that one? comparing 
* y-coordinates and breaking ties by x-coordinates 
*/ 
public int compareTo(Point that) { 
    // TODO: Implement this 
    if(this.y < that.y){ 
     return -1; 
    } 
    else if(this.y > that.y){ 
     return 1; 
    } 
    else{ 
     if(this.x < that.x){ 
      return -1; 
     } 
     else if(this.x > that.x){ 
      return 1; 
     } 
     else{ 
      return 0; 
     } 
    } 
} 

这里是我的fast.java类：

private static void getLines(Point[] points) { 
    Point p = points[0]; 
    Point[] lines = new Point[points.length]; 
    lines[0] = p; 
    int pointsOnLine = 0; 
    double lastSlope = p.slopeTo(points[1]); 
    for(int i = 1; i < points.length; i++) { 
     Point newPoint = points[i]; 
     double slope = p.slopeTo(newPoint); 
     if(slope == lastSlope) { 
      pointsOnLine++; 
      lines[pointsOnLine] = newPoint; 
     } 
     else { 
      if(pointsOnLine >= 3) { 
       printLine(lines, pointsOnLine + 1); 
      } 
      pointsOnLine = 1; 
      lines[1] = newPoint; 
     } 
     lastSlope = slope; 
    } 

    if(pointsOnLine >= 3) { 
     printLine(lines, pointsOnLine + 1); 
    } 
} 

private static void printLine(Point[] lines, int size) { 
    Arrays.sort(lines, 1, size); 
    if(lines[0].compareTo(lines[1]) < 0) { 
     StdOut.print(lines[0]); 
     for(int i = 1; i < size; i++) { 
      StdOut.print(" -> " + lines[i]); 
     } 
     StdOut.println(); 
    } 
} 

而我的主要功能

public static void main(String[] args) { 
    In in = new In(); 
    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); 
    } 

    in.close(); 
    Point [] pointsCopy = Arrays.copyOf(points, points.length); 
    for (Point originPoint : points) { 
     Arrays.sort(pointsCopy, originPoint.SLOPE_ORDER); 
     getLines(pointsCopy); 
    } 
} 

个

我的计划产出

(10000, 0) -> (8000, 2000) -> (2000, 8000) -> (0, 10000) 
(10000, 0) -> (13000, 0) -> (20000, 0) -> (30000, 0) 
(30000, 0) -> (20000, 10000) -> (10000, 20000) -> (0, 30000) 
(13000, 0) -> (11000, 3000) -> (9000, 6000) -> (5000, 12000) 

虽然正确的输出是

(10000, 0) -> (8000, 2000) -> (2000, 8000) -> (0, 10000) 
(10000, 0) -> (13000, 0) -> (20000, 0) -> (30000, 0) 
(13000, 0) -> (11000, 3000) -> (9000, 6000) -> (5000, 12000) 
(30000, 0) -> (20000, 10000) -> (10000, 20000) -> (0, 30000) 

任何人都可以看到我要去哪里错了吗？ 谢谢。

Answer 1

输出将按照pointsCopy数组内的顺序出现。 Arrays.sort按照导致输出的方式进行排序。您可以重新排列pointsCopy数组中的元素或更改数组排序逻辑以获得所需的输出。