问题描述
给定2维平面上n个整点的坐标，一条直线最多能过几个点？
输入格式
第一行一个整数n表示点的个数
以下n行，每行2个整数分别表示每个点的x,y坐标。
输出格式
输出一个整数表示答案。
样例输入
5
0 0
1 1
2 2
0 3
2 3
样例输出
3
数据规模和约定
n<=1500，数据保证不会存在2个相同的点。
点坐标在int范围内
题目链接：“蓝桥杯”练习系统
解析：用哈希表关键字与键值映射即可，斜率当关键字，每有一个点在此直线上不断加一即可。话不多说，直接上代码，代码附注释。
#include<iostream> #include<utility> #include<map> using namespace std; pair<int,int> a[2000];//输入二维坐标，用pair或结构体 int n,maxx; int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i].first>>a[i].second;//输入位置 } map<double,int> p;//用map映射 for(int i=0;i<n;i++){//始点 for(int j=i+1;j<n;j++){//终点 double k;//斜率 k=double(a[i].second-a[j].second)/(a[i].first-a[j].first);//强转为double,否则数据会四舍五入 if(p[k]==0){//如果此次斜率是第一次出现，说明两点构成一条直线，点数为2，需要多加一次 p[k]++; } p[k]++;//如果存在了那就再此基础上加一即可 maxx=max(p[k],maxx);//寻找最大值 } p.erase(p.begin(),p.end());//暴力枚举，若不清空，会影响下一个始点的计算 //我们是先固定起点，再遍历终点，求斜率 //若有三个点构成一条直线，第一次固定第一个点为始点，终点遍历后面两个点，此时为点数3 //若不清空继续遍历，第二个点为始点，第三个点为终点，p[k]++还会继续，变为4，重复计算，所以清空 } cout<<maxx<<endl; return 0; }
此题是本人的思路，小白一枚，若有更好的方法，欢迎各位大佬讨论。
