题意：
给n个点，其中最多有多少点共线（n<1000）。
分析：
这是一个经典问题，朴素n^3解法：枚举n^2条直线，判断每条直线与多少点相交，复杂度n^3。明显会超时。这是n^2logn的解法：枚举每个点，对某个点与其他点连的n条直线按斜率排序，设这些直线中斜率相同的直线有k条，则k更新答案。这里想着重说一下斜率的问题，网上很多代码都是直接算斜率的，但计算几何的题目不推荐用斜率，最好用叉积代替有关斜率的一切计算，因为1）斜率的取值范围非常大，如果有中间计算有乘法很容易爆数据表示范围，对于要求精度的题会捉急。2）如果你定义INF=100000000代表无穷大的斜率，那么如果题目中有条直线的斜率为INF+1怎么办？3）计算斜率涉及除法，处处要特判分母，导致程序不简洁还容易出错4）叉积和点积是对点线关系比斜率深刻得多的描述，能表示点线之间的前后关系，顺逆关系等，，有时候将点线平移还能在叉积点积运算上构成偏序集（这道题代码中对线段的逆向就是为了构成偏序集），而偏序集又可以多出很多手段来处理了。所以建议计算几何中少考虑斜率，多从点积叉积开始入手。
代码：
//poj 2780//sep9#include <iostream>#include <algorithm> #include <cmath>using namespace std;const int maxN=1024;const int maxM=500024;struct POINT{int x,y;}p[maxN];struct LINE{int x,y;}l[maxM];int cmp(LINE a,LINE b){ return a.x*b.y-a.y*b.x>=0;}int main(){int n;while(scanf("%d",&n)==1){int num_line,ans=-1;for(int i=0;i<n;++i)scanf("%d%d",&p[i].x,&p[i].y);for(int i=0;i<n;++i){num_line=0;for(int j=i+1;j<n;++j){int dx=p[i].x-p[j].x,dy=p[i].y-p[j].y;if(dy<0) dy=-dy,dx=-dx;else if(dy==0&&dx<0)dx=-dx;l[num_line].x=dx,l[num_line].y=dy;++num_line;}sort(l,l+num_line,cmp);int cnt=0;for(int k=0;k<num_line;++k)if(k==0||l[k-1].x*l[k].y==l[k-1].y*l[k].x)++cnt;else{ans=max(ans,cnt);cnt=1;}ans=max(ans,cnt);}printf("%d\n",ans+1);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
诚实是人生绝妙的法宝。虽然对人诚实，
