给平面上的n个点，找到在一条线上数量最多的。
一种方法是在n个点钟找到两个点算出斜率，然后枚举其他点，若在通一条直线上，计数器加一。效率为O(n^3).
第二种方法是对于一个点，算出所有的斜率，排序O（nlgn），两个邻近的斜率相同，计数器加一。效率为O（n^2lgn）
以下给出两种算法：
朴素方法：
/*#include<iostream>
using namespace std;
#define MAX 700
struct POINT
{
int x, y;
}point[MAX];
int main()
{
int i, j, k;
int n, max, temp, a, b;
while(cin>>n)
{
if(n==0){break;}
max = 0;
for(i=0; i<n; i++)
cin>>point[i].x>>point[i].y;
for(i=0; i<n; i++)
{
for(j=i+1; j<n; j++)
{
temp = 0;
a = point[j].y - point[i].y;
b = point[j].x - point[i].x;
for(k=j+1; k<n; k++)
if(a * (point[k].x - point[i].x) == (point[k].y - point[i].y) * b)
temp++;
if(max < temp)
max = temp;
}
}
cout<<max+2;
}
return 0;
}
编程网格时间：
Case 0: Time = 5ms, Memory = 272kB. Case 1: Time = 5ms, Memory = 272kB. Case 2: Time = 5ms, Memory = 272kB. Case 3: Time = 5ms, Memory = 272kB. Case 4: Time = 6ms, Memory = 272kB. Case 5: Time = 12ms, Memory = 272kB. Case 6: Time = 31ms, Memory = 272kB. Case 7: Time = 43ms, Memory = 272kB. Case 8: Time = 73ms, Memory = 272kB. Case 9: Time = 73ms, Memory = 272kB. Case 10: Time = 80ms, Memory = 272kB. Case 11: Time = 87ms, Memory = 272kB. Case 12: Time = 88ms, Memory = 272kB. Case 13: Time = 124ms, Memory = 272kB. Case 14: Time = 158ms, Memory = 272kB. Case 15: Time = 220ms, Memory = 272kB. Case 16: Time = 369ms, Memory = 272kB. Case 17: Time = 367ms, Memory = 272kB.
优化方法：
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 700
struct POINT
{
int x, y;
}point[MAX];
int N;
double angle[MAX];
int compare(void const*p,void const *q)
{
double *temp1=(double*)p;
double *temp2=(double*)q;
return (*temp1)>(*temp2)?1:-1;
};
int main()
{
while(cin>>N)
{
if(N==0){break;}
for(int i=0; i<N; i++)
cin>>point[i].x>>point[i].y;
int max=0;
for(int i=0;i<N-1;i++)
{
int index=0;
memset(angle,0,sizeof(double));
for(int j=i+1;j<N;j++)
{
if(point[i].x==point[j].x)
{
angle[index++]=0;
}
else
{
angle[index++]=(double)(point[j].y-point[i].y)/(point[j].x-point[i].x);
}
}
qsort(angle,index,sizeof(double),compare);
int temp=0;
for(int j=1;j<index;j++)
{
if(angle[j]==angle[j-1])
{
temp++;
}
else
{
if(temp>max)
{
max=temp;
temp=0;
}
}
}
if(temp>max){max=temp;}
}
cout<<max+2<<endl;
}
return 0;
}
编程网格时间：
Case 0: Time = 5ms, Memory = 272kB. Case 1: Time = 5ms, Memory = 272kB. Case 2: Time = 6ms, Memory = 272kB. Case 3: Time = 5ms, Memory = 272kB. Case 4: Time = 6ms, Memory = 272kB. Case 5: Time = 8ms, Memory = 272kB. Case 6: Time = 14ms, Memory = 272kB. Case 7: Time = 18ms, Memory = 272kB. Case 8: Time = 29ms, Memory = 272kB. Case 9: Time = 30ms, Memory = 272kB. Case 10: Time = 32ms, Memory = 272kB. Case 11: Time = 32ms, Memory = 272kB. Case 12: Time = 40ms, Memory = 272kB. Case 13: Time = 41ms, Memory = 272kB. Case 14: Time = 52ms, Memory = 272kB. Case 15: Time = 54ms, Memory = 272kB. Case 16: Time = 63ms, Memory = 272kB. Case 17: Time = 73ms, Memory = 272kB.
可以发现对于后几组数据效率有明显提高。