Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:无误差 gcd求解法

Posted by dakecaoxin at 2010-02-19 18:31:13 on Problem 2780
In Reply To:无误差 gcd求解法 Posted by:runformydream at 2009-09-06 10:54:47
```> 由于每条直线的斜率相同，所以其斜率 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;
> }
```

Followed by:

User ID:
Title:

Content: