finding the maximum number of points that lie on the same straight line in a 2D plane

Question

This "Given n points on a 2D plane, find the maximum number of points that lie on the same straight line." question from leetcode.com I am trying to solve it but I am not able to pass all test cases.

What I am trying to do is:- I am using a hashmap whose key is the angle b/w the points which I am getting through tan inverse of the slope and I am storing the values for each slope initially the value of the no of occurrance of that point and then incrementing it.

I am using another hashmap for counting the occurance of points.

I am not getting the correct answer for points like (0,0),(1,0) which should return 2 but it's returning 1.

What am I missing?

My code is:

public class MaxPointsINLine {
    int max = 0;
    int same;

    public int maxPoints(Point[] points) {
        int max = 0;
        Map<Double, Integer> map = new HashMap<Double, Integer>();
        Map<Point, Integer> pointmap = new HashMap<Point, Integer>();
        for(Point point: points)
        {
            if(!pointmap.containsKey(point))
            {
                pointmap.put(point, 1);
            }
            else
            {
                pointmap.put(point, pointmap.get(point)+1);
            }
        }
        if (points.length >= 2) {
            for (int i = 0; i < points.length; i++) {
                for (int j = i ; j < points.length; j++) {
                    double dx = points[j].x - points[i].x;
                    double dy = points[j].y - points[i].y;
                    double slope = Math.atan(dy / dx);
                    if (!map.containsKey(slope)) {
                        map.put(slope, pointmap.get(points[j]));
                    } else
                        map.put(slope, map.get(slope) + 1);
                }
            }
            for (Double key : map.keySet()) {
                if (map.get(key) > max) {
                    max = map.get(key);
                }
            }
            return max;
        } else if (points.length != 0) {
            return 1;
        } else {
            return 0;
        }
    } 

    public static void main(String[] args) {
        Point point1 = new Point(0,0);
        Point point2 = new Point(0,0);
        //Point point3 = new Point(2,2);
        MaxPointsINLine maxpoint = new MaxPointsINLine();
        Point[] points = { point1, point2};
        System.out.println(maxpoint.maxPoints(points));

    }

}

class Point {
    int x;
    int y;

    Point() {
        x = 0;
        y = 0;
    }

    Point(int a, int b) {
        x = a;
        y = b;
    }

    @Override
    public boolean equals(Object obj) {
        Point that = (Point)obj;
        if (that.x == this.x && that.y == this.y)
            return true;
        else
            return false;
    }

    @Override
    public int hashCode() {
        // TODO Auto-generated method stub
        return 1;
    }
}

Answer 1

The general strategy doesn't seem like it can work. Let's suppose that we've successfully populated map with key-value pairs (a, N) where a is an angle and N is the number of pairs of points that are joined by the angle a. Consider the following arrangement of 6 points:

**
  **
**

Explicitly, there are points at (0,0), (1,0), (2,1), (3,1), (0,2), and (1,2). You can check that the maximum number of points that lie on any line is 2. However, there are 3 pairs of points that are joined by the same angle: ((0,0), (1,0)), ((2,1), (3,1)), and ((0,2), (1,2)). So map will contain a key-value pair with N = 3, but that isn't the answer to the original question.

Because of arrangements like the above, it's not enough to count slopes. A successful algorithm will have to represent lines in such a way that you can distinguish between parallel lines.

Answer 2

This one worked for me:

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {


        int result = 0;
        for(int i = 0; i<points.length; i++){
            Map<Double, Integer> line = new HashMap<Double, Integer>();
            Point a = points[i];
            int same = 1;    
            //System.out.println(a);
            for(int j = i+1; j<points.length; j++){
                Point b = points[j];
                //System.out.println(" point " + b.toString());
                if(a.x == b.x && a.y == b.y){
                    same++;
                } else {
                    double dy = b.y - a.y;
                    double dx = b.x - a.x;
                    Double slope;
                    if(dy == 0){ // horizontal
                        slope = 0.0;
                    } else if(dx == 0){//eartical
                        slope = Math.PI/2;
                    } else {
                        slope = Math.atan(dy/dx);
                    }
                    Integer slopeVal = line.get(slope);
                    //System.out.println(" slope " + slope + "  slope value " + slopeVal);
                    if(slopeVal == null){
                        slopeVal = 1;
                    } else {
                        slopeVal += 1;
                    }
                    line.put(slope, slopeVal);
                }
            }

            for (Double key : line.keySet()) {
                Integer val = line.get(key);
                result = Math.max(result, val + same);
            }
            // for all points are same
            result = Math.max(result, same);

        }
        return result;
    }



}