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;}
