大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168550.html原文链接：https://javaforall.net
