由于每条直线的斜率相同，所以其斜率 k=b/a,(gcd(b,a)=1)都相同，运用此定理，可以写出n^2log(n)的算法,即对每个点，求k的两个参数，然后排序一遍比较即可，注意符号问题，数据MS会出现负数

代码:
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define N 1010
struct Node{
       int x,y;
}num[N],ps[N];
int compare(const void *a,const void *b){
    struct Node f=*(struct Node *)a;
    struct Node s=*(struct Node *)b;    
    if(f.x==s.x)  return f.y-s.y;
    return f.x-s.x;
}
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b); 
}
int HGcd(int y,int x){
    x=abs(x);
    y=abs(y);
    return gcd(max(x,y),min(x,y));
}
int n;
int main(){
    int i,j,zeroNum,maxNum,MAX,k,x,y,pp,count;
    while(scanf("%d",&n)!=EOF){
         for(i=1;i<=n;i++) scanf("%d%d",&num[i].x,&num[i].y);
         if(n==1) {
              printf("1\n");
              continue;
         }else if(n==2){
               printf("2\n");
               continue;
         }
         MAX=-1;
         for(i=1;i<=n;i++){
               zeroNum=0,maxNum=0;
               k=0;
               for(j=i+1;j<=n;j++){
                       if(i==j) continue;
                       y=num[i].y-num[j].y;
                       x=num[i].x-num[j].x;
                       if(x==0&&y==0) x=0,x=1/x;
                       else if(y==0) zeroNum++;
                       else if(x==0) maxNum++;
                       else{
                            pp=HGcd(x,y);
                            ps[k].x=x/pp;
                            ps[k].y=y/pp;
                            if(ps[k].y<0){
                                ps[k].y=-ps[k].y;
                                ps[k].x=-ps[k].x;
                            }
                            k++;
                       }
               }
               qsort(ps,k,sizeof(ps[0]),compare);
               MAX=max(MAX,zeroNum);
               MAX=max(MAX,maxNum);
               if(k>0){
                  count=1;
                  for(j=1;j<k;j++){
                       if((ps[j].x==ps[j-1].x)&&(ps[j].y==ps[j-1].y)){
                             count++;
                       }else{
                            MAX=max(MAX,count);
                            count=1;
                       }
                  }
                  MAX=max(MAX,count);
               }
         }
         printf("%d\n",MAX+1);
    }
    return 0;
}

• Re:无误差 gcd求解法 (2593) dakecaoxin 2010-02-19 18:31:13