题目及题目来源
链接：https://www.nowcoder.com/questionTerminal/bfc691e0100441cdb8ec153f32540be2
来源：牛客网
首页 > 试题广场 > max-points-on-a-line
[编程题]max-points-on-a-line
热度指数：67696 时间限制：1秒 空间限制：32768K
算法知识视频讲解
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
题解 及完整类
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int high=0; //++high mode
struct Point {
int x;
int y;
Point() : x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
};
/*
链接：https://www.nowcoder.com/questionTerminal/bfc691e0100441cdb8ec153f32540be2
来源：牛客网
需要两重循环，第一重循环遍历起始点a，第二重循环遍历剩余点b。
a和b如果不重合，就可以确定一条直线。
对于每个点a，构建 斜率->点数 的map。
(1)b与a重合，以a起始的所有直线点数+1 (用dup统一相加)
(2)b与a不重合，a与b确定的直线点数+1
*/
class Solution {
public:
int maxPoints(vector<Point> &points) {
int size=points.size();
if(size==0)return 0;
else if(size==1)return 1;
else if(size==2) return 2;
int ret=0;
for(int i=0;i<size;i++){ //遍历起点a
map<double,int>mp; //构建斜率->点数的map集合
int vcent=0; //垂直的点
int dub=0; //重合的点
for(int j=0;j<size;j++){ //枚举起点b
if(i==j)continue;
//确定x,y的差值: x1,x2
double x1 = points[i].x-points[j].x;
double y1 = points[i].y-points[j].y;
//重合的情况
if(x1==0&&y1==0){
dub++;
ret=max(ret,dub+1);
} //垂直线上的情况
else if(x1==0){
vcent++;
ret=max(ret,1+dub+vcent);
}
// 求出斜率,保存到map中
else{
double k=y1/x1;
mp[k]++;
ret=max(ret,1+dub+mp[k]);
}
// cout<<"i= "<<i<<" j="<<j<<" ret="<<ret;
// printf(" dub=%d vent=%d\n",dub,vcent);
}
// cout<<endl;
}
return ret;
}
};
//void debug(vector<Point> points){ //输出重复的点的情况,并且最后输出去重的vector表
// int len=points.size();
//
// map<int,int>mp;
//
// for(int i=0;i<points.size();i++){
// for(int j=points.size()-1;j>i;j--){
// if(points[i].x==points[j].x&&points[i].y==points[j].y){
// mp[i]++;
// points.erase(points.begin()+j);
// j=points.size();
// }
// }
// }
// map<int,int>::iterator it=mp.begin();
// for(;it!=mp.end();it++){
// cout<<it->first<<"******"<<it->second<<endl;
// }
// cout<<endl;
//}
int main(){
int n;
char arr[12][12];
memset(arr,' ',sizeof(arr));
while(1){
cin>>n;
vector<Point>p;
int x,y;
for(int i=0;i<n;i++){
scanf("%d%d",&x,&y);
p.push_back(Point(x,y));
// arr[x][y]='*';
}
debug(p);
Solution s;
cout<<s.maxPoints(p)<<endl;
}
// cout<<"_____________________"<<endl;
// for(int i=0;i<10;i++){
// arr[i][11]='\0';
// cout<<arr[i]<<endl;
// }
// cout<<"_____________________"<<endl;
return 0;
}
简单测试数据
/*
思路: 穷举,
用例:
9
84 250 0 0 1 0 0 -70 0 -70 1 -1 21 10 42 90 -42 -230
3
1 1 1 1 1 1
4
1 1 1 1 1 1 2 3
5
1 1 1 1 1 1 2 3 2 3
6
1 1 1 1 1 1
2 3 2 3 4 67
1
0 0
用例:
[(84,250),(0,0),(1,0),(0,-70),(0,-70),(1,-1),(21,10),(42,90),(-42,-230)]
对应输出应该为:
6
你的输出为:
96 7 8 9 2 6 4 7 2 9
*/
/*
ctrl+E ,复制行
ctrl+shift+A :整体缩进对齐
ctrl+D: 删除当前行
*/