对于给定的n个位于同一二维平面上的点，求最多能有多少个点位于同一直线上java实现

题目描述

对于给定的n个位于同一二维平面上的点，求最多能有多少个点位于同一直线上。

思路：依次遍历所有点，计算两点的斜率（考虑重合点和垂直点的特殊情况），非重合斜率相等的点则位于同一直线上。采用Map存储斜率，其中key值设为Double型的斜率，value值为Integer型的点数。

注意：

Map接口中的常用方法

put方法：将指定的键与值对应起来，并添加到集合中。使用put方法时，若指定的键(key)在集合中存在，则返回值为集合中键对应的值（该值为替换前的值），并把指定键所对应的值，替换成指定的新值。若指定的键(key)在集合中不存在，则没有这个键对应的值，返回null，并把指定的键值添加到集合中。

get方法：获取指定键(key)所对应的值(value)。

 

值得注意的是，当斜率计算为0（即两点在一条水平线上）时，要考虑Java double数据类型中的0.0和-0.0问题，HashMap里-0.0和0.0是不同的key。 解决办法： 对获得的double类型数据加上一个0.0。

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
import java.util.*;
public class Solution {
    public int maxPoints(Point[] points) {
        if(points==null)
            return 0;
        if(points.length<3)
            return points.length;
        int i,j;
        double k;
        int res=0;
        for(i=0;i<points.length;i++){
            int same=0;
            int ver=1;
            int num=1;
            Map<Double,Integer> hash=new HashMap<Double,Integer>();
            for(j=i+1;j<points.length;j++){
                if(points[i].x==points[j].x&&points[i].y==points[j].y){
                    same++;
                }
                else if(points[i].x==points[j].x&&points[i].y!=points[j].y){
                    ver++;
                    num=Math.max(num,ver);
                }
                else{
                    double dy=points[j].y-points[i].y;
                    double dx=points[j].x-points[i].x;
                    k=dy/dx+0.0;
                    if(hash.get(k)==null){
                        hash.put(k,2);
                    }
                    else{
                        hash.put(k,hash.get(k)+1);
                    }
                    num=Math.max(num,hash.get(k));
                }
            }
            res=Math.max(res,num+same);
        }
        return res;
    }
}