在排序上找到一個斜坡上的點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數組中的元素或更改數組排序邏輯以獲得所需的輸出。