Different answer ON OJ and local machine(Java)


  • 1
    Y

    OJ gives
    [(0,0),(1,1),(-1,1)]
    Output: 3
    Expected: 2

    However, in my machine, the output is 2 instead of 3. Is there any mistakes?

    My code is slow (O(n^3)), this is the first idea.

    public class Solution {
    
        public int maxPoints(Point[] points) {
            if (points.length == 0) {
                return 0;
            }
            if (points.length <= 2) {
                return points.length;
            }
            
            int maxPoint = 0;
            for(int i = 0; i < points.length - 1; i ++) {
                for (int j = i + 1; j < points.length; j ++) {
                    Line tmp = calculateLine(points[i].x, points[i].y, points[j].x, points[j].y);
                    if (tmp == null) {
                        continue;
                    }
                    int count = 2;
                    for (int k = 0; k < points.length; k ++) {
                        if(k != i && k != j) {
                            if (tmp.a ==0 && tmp.b == 0 && points[k].x == points[i].x) {
                                ++ count;
                            }else if (isInLine(points[k], tmp)) {
                                ++ count;
                            }
                        }
                    }
                    if (maxPoint < count) {
                        maxPoint = count;
                    }
                }
            }
            return maxPoint;
        }
        
        boolean isInLine(Point point, Line line){
            if ( (line.a * point.x + line.b) - point.y < 0.000001 || (point.y - (line.a * point.x + line.b)) < 0.000001) {
                return true;
            }
            return false;
        }
        
        Line calculateLine(int x1, int y1, int x2, int y2) {
            if (y2 == y1 && x2 == x1) {
                return null;
            } else if (y2 == y1 && x2 != x1) {
                return new Line(0, y1);
            } else if (x2 == x1 && y2 != y1) {
                return new Line(0, 0);
            } else {
                double a = (y2 - y1) / (double) (x2 - x1);
                double b = (x2 * y1 - x1 * y2) / (double) (x2 - x1);
                return new Line(a,b);
            }
        }
        
        class Line {
            double a;
            double b;
            Line() {
                a = 0;
                b = 0;
            }
            Line(double a, double b) {
                this.a = a;
                this.b = b;
            }
        }
    }

  • 0
    H
    if ( (line.a * point.x + line.b) - point.y < 0.000001d && (point.y - (line.a * point.x + line.b)) < 0.000001d) {
                return true;
    }
    

    Shouldn't you write this?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.