蓝桥杯练习系统（算法训练）ALGO-967 共线

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　给定2维平面上n个整点的坐标，一条直线最多能过几个点？

输入格式

　　第一行一个整数n表示点的个数
　　以下n行，每行2个整数分别表示每个点的x,y坐标。

输出格式

　　输出一个整数表示答案。

样例输入

5
0 0
1 1
2 2
0 3
2 3

样例输出

3

数据规模和约定

　　n<=1500，数据保证不会存在2个相同的点。
　　点坐标在int范围内

暴力（只有87分）

#include<iostream>
using namespace std;
const int N=1505;
typedef struct Point{
	int x;
	int y;
}Point; 
Point point[N];
int n;
int ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>point[i].x>>point[i].y;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){//形成斜率 
			int cnt=0;
			int xx=point[j].x-point[i].x;
			int yy=point[j].y-point[i].y;
			for(int k=1;k<=n;k++){//找点，使之斜率相等或本身的那个点 
				if(xx*(point[i].y-point[k].y)==yy*(point[i].x-point[k].x)){
					cnt++;
				}
			}
			ans=max(ans,cnt); 
		}
	}
	cout<<ans<<endl;
	return 0;
} 

哈希表（但是5.11版本不能用）

#include <iostream>
#include <unordered_map>
#include <math.h>
using namespace std;
const int N=1505;
typedef struct Point{
	int x;
	int y;
}Point; 
Point point[N];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <=n; i++) {
        cin >> point[i].x >> point[i].y;
    }
    int result = 0;
    if (n <= 2) {
        result=n;
    }else{
    	unordered_map<double, int> slopeCount;
    	for (int i =1; i <=n; i++){
	        for (int j =i+1; j <=n; j++){
	            int dx = point[j].x - point[i].x;
	            int dy = point[j].y - point[i].y;
	            double slope; 
	            if(dx==0){
	            	slope=0x3f3f3f3f;
				}else{
					slope=(double)dy / dx;
				} 
	            slopeCount[slope]++;
	            result= max(result,slopeCount[slope]);//直线斜率相等，同一直线上的点个数n和斜率相等的个数的关系：n(n-1)/2=斜率相等的个数 
	        }
   		}
   		result=sqrt(2*result)+1;
	}
	cout<<result<<endl;
    return 0;
}