leetcode难度级别_直线上最多的点数

全栈程序员-用户IM • 2022年8月9日下午4:16 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

示例 1:

输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4
示例 2:

输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

const double eps = 1e-10;
const int N = 1e3 + 10;
bool cmp(const double &a,const double &b){ 
   
    return abs(a - b) < eps;
}
struct Node{ 
   
    double k;
    Node(double _k){ 
   
        k = _k;
    }
    bool operator<(const Node &b)const{ 
   
        if(cmp(k,b.k))return false;
        else return k < b.k;
    }
};
class Solution { 
   
public:
    map<Node,int>m;
    int maxPoints(vector<vector<int>>& points) { 
   
        int ans = 0;
        int n = points.size();
        if(n == 1 || n == 0)return n;
        for(int i = 0;i < n;i ++){ 
   
            m.clear();
            int same = 0;
            for(int j = 0;j < n;j ++){ 
   
                if(j == i)continue;
                int x1 = points[i][0],y1 = points[i][1];
                int x2 = points[j][0],y2 = points[j][1];
                if(x1 == x2){ 
   
                    same ++;
                    continue;
                }
                Node t(double(y1 - y2) / (x1 - x2));
                if(m.find(t) == m.end())m[t] = 0;
                m[t] ++;
            }
            for(auto &a : m){ 
   
                ans = max(ans,a.second);
            }
            ans = max(ans,same);
        }
        return ans + 1;
    }
};