Description “How am I ever going to solve this PRoblem?” said the pilot.
Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the pilot could only fly over the area once in a straight line, and she had to fly over as many points as possible. All points were given by means of integer coordinates in a two-dimensional space. The pilot wanted to know the largest number of points from the given set that all lie on one line. Can you write a program that calculates this number?
Your program has to be efficient! Input Input consist several case,First line of the each case is an integer N ( 1 < N < 700 ),then follow N pairs of integers. Each pair of integers is separated by one blank and ended by a new-line character. The input ended by N=0. Output output one integer for each input case ,representing the largest number of points that all lie on one line. Sample Input 5 1 1 2 2 3 3 9 10 10 11 0 Sample Output 3
题解
超时代码
估算复杂度的时候少乘了个7，不料超时了，复杂度o(n3)
#include<stdio.h>#define MAX_N 1000typedef long long LL;int main(){ int n,x[MAX_N],y[MAX_N]; while(scanf("%d",&n)&&n){ for(int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]); int ans=0; for(int j=0;j<n;j++){ for(int k=j+1;k<n;k++){ int cnt=2; int oy=y[j]-y[k]; int ox=x[j]-x[k]; for(int i=k+1;i<n;i++){ LL tmp=(LL)1*oy*(x[i]-x[j])-(LL)1*ox*(y[i]-y[j]); if(tmp==0) cnt++; } if(cnt>ans) ans=cnt; } } printf("%d/n",ans); } return 0;}不料稍微修改后又ac了，无语啊啊啊，按复杂度算的话最糟的情况得运行 7003/4=85,750,000 次，貌似可以过（给自己打脸了）
#include<stdio.h>#define MAX_N 1000typedef long long LL;int main(){ int n,x[MAX_N],y[MAX_N]; while(scanf("%d",&n)&&n){ for(int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]); int ans=0; for(int j=0;j<n;j++){ for(int k=j+1;k<n;k++){ int cnt=2; int oy=y[j]-y[k]; int ox=x[j]-x[k]; for(int i=k+1;i<n;i++){ int tmp=oy*(x[i]-x[j])-ox*(y[i]-y[j]); if(tmp==0) cnt++; } if(cnt>ans) ans=cnt; } } printf("%d/n",ans); } return 0;}可行方法
得想办法把每一条直线保存下来，再看在直线上有多少个点，复杂度o(n2) 怎么存呢 由于直线的一般方程是 ax+by+c=0 只要保存3个参数 a,b,c 并保证 gcd(a,b,c)=1 ，就可以确定一条直线了
n 个点，两两组合共n2/2 种，空间复杂度就是o(n2) 再对n2/2 条线排序，复杂度o(n2logn) 再用取尺法得到相同的直线的数目，复杂度o(n2)
综上便得到了时间复杂度o(n2logn) ，空间复杂度o(n2) 的算法了
#include<stdio.h>#include<math.h>#include<algorithm>#define MAX_N 710*700/2using namespace std;typedef long long LL;struct node{ int a,b,c;//ax+by+c=0};node L[MAX_N];bool cmp(node x,node y){ if(x.a!=y.a) return x.a<y.a; if(x.b!=y.b) return x.b<y.b; return x.c<y.c;}int gcd(int a,int b){ return b?gcd(b,a%b):a;}int main(){ int n,x[MAX_N],y[MAX_N]; while(scanf("%d",&n)&&n){ for(int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]); int t=0; for(int j=0;j<n;j++){ for(int k=j+1;k<n;k++){ int A=y[j]-y[k]; int B=x[j]-x[k]; int C=-A*x[j]+B*y[j]; int d=gcd(A,B); d=gcd(d,C);if(!d) d=1; if(A/d<0) d=-d;//强制A为正数 L[t++]={A/d,B/d,C/d}; } } sort(L,L+t,cmp); int ans=0;int i=1,r=0; for(;i<t;i++){ if(L[i].a!=L[r].a||L[i].b!=L[r].b||L[i].c!=L[r].c){ int tmp=sqrt((i-r)*2)+1; if(tmp>ans) ans=tmp; r=i; } } int tmp=sqrt((i-r)*2)+1; if(tmp>ans) ans=tmp; printf("%d/n",ans); } return 0;}
