同一直线最大点数问题

数据结构

原题：
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.即：给定二维平面中的n点，求过同一直线的点最多的点

分析：
可以通过双重循环遍历。第一层循环遍历不同的点作为主导点，第二层循环遍历剩下的点，考虑其斜率。有几个细节:
1. 统计斜率和点的数量可以用HashMap
2. 需要考虑斜率不存在的情况
3. 需要考虑点重合的情况，同一点不重复计数

import java.util.*;
class Point {
    int x;
    int y;
    Point() { x = 0; y = 0; }
    Point(int a, int b) { x = a; y = b; }
}
public class MaxPointsOnOneLine {
    public int maxPoints(Point[] points) {
        int n = points.length;
        if(n < 2) return n;
        int ret = 0;
        for(int i = 0; i < n; i++) {
            // 分别统计与点i重合以及垂直的点的个数
            int dup = 1, vtl = 0;
            Map<Float, Integer> map = new HashMap<>();
            Point a = points[i];
            for(int j = 0; j < n; j++) {
                if(i == j) continue;    //同一个点
                Point b = points[j];
                if(a.x == b.x) {
                    if(a.y == b.y) dup++;//重叠的点
                    else vtl++;         //垂直的点
                } else {                //一般情况，根据斜率划分
                    float k = (float)(a.y - b.y) / (a.x - b.x);
                    if(map.get(k) == null) map.put(k, 1);
                    else map.put(k, map.get(k) + 1);
                }
            }
            int max = vtl;          //初始化为垂直的点
            for(float k: map.keySet()) {
                max = Math.max(max, map.get(k));
            }
            ret = Math.max(ret, max + dup);//ret需要加上本身的点
        }
        return ret;
    }
}