Lining Up ``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 The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The input consists of N pairs of integers, where 1 < N < 700. Each pair of integers is separated by one blank and ended by a new-line character. The list of pairs is ended with an end-of-file character. No pair will occur twice. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output consists of one integer representing the largest number of points that all lie on one line. Sample Input 1 1 1 2 2 3 3 9 10 10 11 Sample Output 3 本以為這題用枚舉會超時 結果卻過了，給了我一個小驚喜。 只是此題要注意的時候 輸入的做標可能有負的 [cpp] #include <stdio.h> #include <string.h> #include <math.h> #define EQS 1e-7 struct { double x,y; }a[10000]; char s1[10000]; int main() { int i,j,n,m,t,l,tag,max,z,s; double k1,d1,x1,y1,x2,y2,x3,y3; scanf("%d%*c",&t); gets(s1); while(t--) { n=0; while(gets(s1)) { l=strlen(s1); if(l==0) { break; } if(s1[0]=='-') { i=1; }else { i=0; } for(s=0;i<=l-1;i++) { if(s1[i]==' ') { break; } s=s*10+s1[i] - '0'; } if(s1[0]=='-') { s=s*-1; } a[n].x= (double)s; if(s1[i+1]=='-') { j=i+2; }else { j=i+1; } for(s=0;j <= l-1; j++) { s=s*10 + s1[j]- '0'; } if(s1[i+1]=='-') { s=s*-1; } a[n].y= (double)s; n++; } for(i=0,max=0;i<=n-1; i++) { for(j=i+1; j<=n-1;j++) { x1 = a[i].x; y1= a[i].y; x2 = a[j].x; y2= a[j].y; if(fabs(x2 -x1)<=EQS) { tag=0; d1=x1; }else { tag=1; k1= (y2 - y1)/(x2 - x1); d1= y1 - k1 * x1; } for(z= j+1,s=2;z<=n-1; z++) { if(z==i||z==j) { continue; } x3= a[z].x; y3= a[z].y; if(tag==0&&fabs(x3-x1)<=EQS) { s++; }else if(tag==1&&fabs(k1 * x3 +d1- y3)<= EQS) { s++; } } if(s>max) { max=s; } } } printf("%d\n",max); if(t) { printf("\n"); } } return 0; }
