这给定n在2D平面上的点，发现趴在同一条直线上点的最大数量。 从莱特code.com问题，我试图解决这个问题，但我不能够通过所有测试 案例。

我所试图做的是： - 我使用一个HashMap的关键是角B / W，我正在通过斜坡晒黑倒数得到，我存储每个斜坡最初的值值点在没有该点发生之，然后递增它。

我使用的另一个HashMap的计数点的次数。

我没有得到像点的正确答案（0,0），（1,0），它应该返回2，但它的返回1。

我在想什么？

我的code是：

 公共类MaxPointsINLine {
    INT最大= 0;
    INT相同;

    公众诠释maxPoints（点[]点）{
        INT最大= 0;
        地图＆LT;双，整数GT;图=新的HashMap＆LT;双，整数GT;（）;
        地图＆LT;点，整数GT; pointmap =新的HashMap＆LT;点，整数GT;（）;
        对于（点点：分）
        {
            如果（！pointmap.containsKey（点））
            {
                pointmap.put（点，1）;
            }
            其他
            {
                pointmap.put（点，pointmap.get（点）+1）;
            }
        }
        如果（points.length＆GT; = 2）{
            的for（int i = 0; I＆LT; points.length;我++）{
                对于（INT J =; J＆LT; points.length; J ++）{
                    双DX =点[J] .X  - 点[I] .X;
                    双DY =点[J] .Y  - 点[I] .Y;
                    双坡= Math.atan（DY / DX）;
                    如果（！map.containsKey（斜率））{
                        map.put（斜率，pointmap.get（点[J]））;
                    } 其他
                        map.put（斜率，map.get（斜率）+ 1）;
                }
            }
            对于（双排键：map.keySet（））{
                如果（map.get（键）GT;最大）{
                    最大= map.get（密钥）;
                }
            }
            返回最大值;
        }否则如果（points.length！= 0）{
            返回1;
        } 其他 {
            返回0;
        }
    }

    公共静态无效的主要（字串[] args）{
        点1点=新的点（0,0）;
        点点2 =新的点（0,0）;
        //点​​POINT3 =新的点（2,2）;
        MaxPointsINLine maxpoint =新MaxPointsINLine（）;
        点[]点= {点1，点2};
        的System.out.println（maxpoint.maxPoints（分））;

    }

}

类Point {
    INT X;
    诠释Ÿ;

    点（） {
        X = 0;
        Y = 0;
    }

    点（INT A，INT B）{
        X = A;
        Y = B：
    }

    @覆盖
    公共布尔等于（obj对象）{
        点=（点）目标文件;
        如果（that.x == this.x和放大器;＆安培; that.y == this.y）
            返回true;
        其他
            返回false;
    }

    @覆盖
    公众诠释哈希code（）{
        // TODO自动生成方法存根
        返回1;
    }
}
 

解决方案

最简单的解决方案在这里似乎是以下几点：一，可以考虑每对点。对于每对中，一个计算彼此点的距离，以连接这两个点的线。如果此距离几乎为零，则点位于就行了。

当这是所有做对，你可以挑其中最高分位于连接线的一对。

当然，这是不是很优雅，因为它是在为O（n ^ 2），并进行一些计算两次。但它是非常简单并且相当可靠。我只是实现这个作为 MCVE 的位置：

我们可以设置左键点击鼠标点。右键点击清屏。被显示在一行的点的最大数目，以及相应的点被突出显示。

（编辑：更新，可以处理为0的距离，基于注释分）

 进口java.awt.BorderLayout中;
进口java.awt.Color中;
进口java.awt.Graphics;
进口java.awt.Graphics2D中;
进口java.awt.Point中;
进口java.awt.event.MouseEvent中;
进口java.awt.event.MouseListener;
进口java.awt.geom.Line2D中;
进口的java.util.ArrayList;
进口的java.util.List;

进口javax.swing.JFrame中;
进口javax.swing.JPanel中;
进口javax.swing.SwingUtilities中;

公共类PointsOnStraightLineTest
{
    公共静态无效的主要（字串[] args）
    {
        SwingUtilities.invokeLater（新的Runnable（）
        {
            @覆盖
            公共无效的run（）
            {
                createAndShowGUI（）;
            }
        }）;
    }

    私有静态无效createAndShowGUI（）
    {
        JFrame的F =新的JFrame（）;
        f.setDefaultCloseOperation（JFrame.EXIT_ON_CLOSE）;
        f.getContentPane（）的setLayout（新的BorderLayout（））。
        。f.getContentPane（）增加（新PointsPanel（））;
        f.setSize（600，600）;
        f.setLocationRelativeTo（空）;
        f.setVisible（真正的）;
    }
}

类PointsOnStraightLine
{
    //大小量，使其更容易放置
    //某些点上，用鼠标一行...
    私有静态最后双EPSILON = 5.0;

    名单＆LT;点＆GT; maxPointsOnLine =新的ArrayList＆LT;点＆GT;（）;

    无效的计算（表＆LT;点＆GT;分）
    {
        maxPointsOnLine =新的ArrayList＆LT;点＆GT;（）;

        的for（int i = 0; I＆LT; points.size（）;我++）
        {
            对于（INT J = I + 1; J＆LT; points.size（）; J ++）
            {
                点P0 = points.get（ⅰ）;
                点P1 = points.get（J）;
                名单＆LT;点＆GT; resultPoints = NULL;
                如果（p0.distanceSq（P1）所述; EPSILON）
                {
                    resultPoints = computePointsNearby（P0，点）;
                }
                其他
                {
                    resultPoints = computePointsOnLine（P0，P1，点）;
                }
                如果（resultPoints.size（）＆GT; maxPointsOnLine.size（））
                {
                    maxPointsOnLine = resultPoints;
                }
            }
        }
    }

    私人列表＆LT;点＆GT; computePointsOnLine（
        点P0，P1点，列表和LT;点＆GT;分）
    {
        名单＆LT;点＆GT;结果=新的ArrayList＆LT;点＆GT;（）;
        对于（INT K = 0; K＆LT; points.size（）; k ++）
        {
            点p = points.get（K）;
            双D = Line2D.ptLineDistSq（p0.x，p0.y，p1.x，p1.y，PX，PY）;
            如果（D＆所述; EPSILON）
            {
                result.add（对）;
            }
        }
        返回结果;
    }

    私人列表＆LT;点＆GT; computePointsNearby（
        点P0，列表和LT;点＆GT;分）
    {
        名单＆LT;点＆GT;结果=新的ArrayList＆LT;点＆GT;（）;
        对于（INT K = 0; K＆LT; points.size（）; k ++）
        {
            点p = points.get（K）;
            双D = p.distanceSq（P0）;
            如果（D＆所述; EPSILON）
            {
                result.add（对）;
            }
        }
        返回结果;
    }

}



类PointsPanel继承JPanel实现的MouseListener
{
    私人最终名单，其中;点＆GT;分;
    私人最终PointsOnStraightLine pointsOnStraightLine;

    PointsPanel（）
    {
        addMouseListener将（本）;

        分=新的ArrayList＆LT;点＆GT;（）;
        pointsOnStraightLine =新PointsOnStraightLine（）;
    }

    @覆盖
    保护无效paintComponent（图形克）
    {
        super.paintComponent方法（克）;
        Graphics2D的G =（Graphics2D的）GR;

        g.setColor（Color.BLACK）;
        对于（点P：分）
        {
            g.fillOval（p.x-2，p.y-2，4，4）;
        }

        pointsOnStraightLine.compute（分）;

        INT N = pointsOnStraightLine.maxPointsOnLine.size（）;
        g.drawString（maxPoints：+ N，10，20）;

        g.setColor（Color.RED）;
        对于（点P：pointsOnStraightLine.maxPointsOnLine）
        {
            g.drawOval（p.x-3，p.y-3，6，6）;
        }
    }

    @覆盖
    公共无效的mouseClicked（的MouseEvent E）
    {
        如果（SwingUtilities.isRightMouseButton（E））
        {
            points.clear（）;
        }
        其他
        {
            points.add（e.getPoint（））;
        }
        重画（）;
    }

    @覆盖
    公共无效鼠标pressed（的MouseEvent E）
    {
    }

    @覆盖
    公共无效的mouseReleased（的MouseEvent E）
    {
    }

    @覆盖
    公共无效的mouseEntered（的MouseEvent E）
    {
    }

    @覆盖
    公共无效的mouseExited（的MouseEvent E）
    {
    }
}
 

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;
    }
}

The most straightforward solution here seems to be the following: One can consider each pair of points. For each pair, one computes the distance of each other point to the line connecting the two points. If this distance is nearly zero, then the point lies on the line.

When this is done for all pairs, one can pick the pair for which the highest number of points lies on the connecting line.

Of course, this is not very elegant, as it is in O(n^2) and performs some computations twice. But it is very simple and rather reliable. I just implemented this as a MCVE here:

One can set points with left-clicking the mouse. Right-clicks clear the screen. The maximum number of points in one line is displayed, and the corresponding points are highlighted.

(EDIT: Updated to handle points that have a distance of 0, based on the comment)

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.util.List;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;

public class PointsOnStraightLineTest
{
    public static void main(String[] args)
    {
        SwingUtilities.invokeLater(new Runnable()
        {
            @Override
            public void run()
            {
                createAndShowGUI();
            }
        });
    }

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.getContentPane().setLayout(new BorderLayout());
        f.getContentPane().add(new PointsPanel());
        f.setSize(600, 600);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }
}

class PointsOnStraightLine
{
    // Large epsilon to make it easier to place
    // some points on one line with the mouse...
    private static final double EPSILON = 5.0; 

    List<Point> maxPointsOnLine = new ArrayList<Point>();

    void compute(List<Point> points)
    {
        maxPointsOnLine = new ArrayList<Point>();

        for (int i=0; i<points.size(); i++)
        {
            for (int j=i+1; j<points.size(); j++)
            {
                Point p0 = points.get(i);
                Point p1 = points.get(j);
                List<Point> resultPoints = null;
                if (p0.distanceSq(p1) < EPSILON)
                {
                    resultPoints = computePointsNearby(p0, points);
                }
                else
                {
                    resultPoints = computePointsOnLine(p0, p1, points);
                }
                if (resultPoints.size() > maxPointsOnLine.size())
                {
                    maxPointsOnLine = resultPoints;
                }
            }
        }
    }

    private List<Point> computePointsOnLine(
        Point p0, Point p1, List<Point> points)
    {
        List<Point> result = new ArrayList<Point>();
        for (int k=0; k<points.size(); k++)
        {
            Point p = points.get(k);
            double d = Line2D.ptLineDistSq(p0.x, p0.y, p1.x, p1.y, p.x, p.y);
            if (d < EPSILON)
            {
                result.add(p);
            }
        }
        return result;
    }

    private List<Point> computePointsNearby(
        Point p0, List<Point> points)
    {
        List<Point> result = new ArrayList<Point>();
        for (int k=0; k<points.size(); k++)
        {
            Point p = points.get(k);
            double d = p.distanceSq(p0);
            if (d < EPSILON)
            {
                result.add(p);
            }
        }
        return result;
    }

}



class PointsPanel extends JPanel implements MouseListener
{
    private final List<Point> points;
    private final PointsOnStraightLine pointsOnStraightLine;

    PointsPanel()
    {
        addMouseListener(this);

        points = new ArrayList<Point>();
        pointsOnStraightLine = new PointsOnStraightLine();
    }

    @Override
    protected void paintComponent(Graphics gr)
    {
        super.paintComponent(gr);
        Graphics2D g = (Graphics2D)gr;

        g.setColor(Color.BLACK);
        for (Point p : points)
        {
            g.fillOval(p.x-2, p.y-2, 4, 4);
        }

        pointsOnStraightLine.compute(points);

        int n = pointsOnStraightLine.maxPointsOnLine.size();
        g.drawString("maxPoints: "+n, 10, 20);

        g.setColor(Color.RED);
        for (Point p : pointsOnStraightLine.maxPointsOnLine)
        {
            g.drawOval(p.x-3, p.y-3, 6, 6);
        }
    }

    @Override
    public void mouseClicked(MouseEvent e)
    {
        if (SwingUtilities.isRightMouseButton(e))
        {
            points.clear();
        }
        else
        {
            points.add(e.getPoint());
        }
        repaint();
    }

    @Override
    public void mousePressed(MouseEvent e)
    {
    }

    @Override
    public void mouseReleased(MouseEvent e)
    {
    }

    @Override
    public void mouseEntered(MouseEvent e)
    {
    }

    @Override
    public void mouseExited(MouseEvent e)
    {
    }
}