HDU1432+几何

题意：给N个点，求最多有多少个点在同一直线上

方法一：求出所有能形成的直线，两两比较，统计最多有多少条重合。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<set>
#include<iostream>
using namespace std;
typedef long long int64;
const int64 maxn = 701;
const int64 maxm = 490005;
const int64 inf = -123456789;
struct Point64{
    int x,y;
}pnt[ maxn ];
struct Node{
    int64 a,b,c;
    int x,y;
}tp[ maxm ];

bool s[ maxn ];
//set<int>s;

void init( int n ){
    for( int i=0;i<n;i++ )
        s[ i ] = false;
}

int64 cmp( Node p1,Node p2 ){
    if( p1.a!=p2.a ) return p1.a<p2.a;
    else if( p1.b!=p2.b ) return p1.b<p2.b;
    else return p1.c<p2.c;
}

int64 gcd( int64 a,int64 b ){
    int64 r;
    while( b ){
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

void solve_gcd( int id ){
    int64 Gcd = gcd( tp[ id ].a,tp[ id ].b );
    Gcd = gcd( tp[ id ].c,Gcd );
    tp[ id ].a /= Gcd;
    tp[ id ].b /= Gcd;
    tp[ id ].c /= Gcd;
}    

int main(){
    int n;
    while( scanf("%d",&n)!=EOF ){
        for( int64 i=0;i<n;i++ ){
            cin>>pnt[i].x>>pnt[i].y;
            //scanf("%lld%lld",&pnt[i].x,&pnt[i].y);
            s[ i ] = false;
        }
    if( n==1||n==2 ){
        printf("%d
",n);
        continue;
    } 
        int cnt = 0;
        for( int i=0;i<n;i++ ){
            for( int j=i+1;j<n;j++ ){
                tp[ cnt ].a = pnt[ i ].y - pnt[ j ].y;
                tp[ cnt ].b = pnt[ j ].x - pnt[ i ].x;
                tp[ cnt ].c = pnt[ i ].x*pnt[ j ].y - pnt[ j ].x*pnt[ i ].y;
                tp[ cnt ].x = i;
                tp[ cnt ].y = j;
                solve_gcd( cnt );
                cnt ++;
            }
        }
        sort( tp,tp+cnt,cmp );
        int64 ans = 2;
        int64 ans_tp = 0;
        int64 prea = inf;
        int64 preb = inf;
        int64 prec = inf;
        for( int i=0;i<cnt;i++ ){
            if(( prea!=tp[ i ].a || preb!=tp[ i ].b || prec!=tp[ i ].c )){
                ans_tp = 2;
                prea = tp[ i ].a;
                preb = tp[ i ].b;
                prec = tp[ i ].c;
                memset( s,false,sizeof( s ) );
                s[ tp[i].x ] = true;
                s[ tp[i].y ] = true;
            }
            else {
                if( s[ tp[i].x ]==false ) {
                    ans_tp ++;
                    s[ tp[i].x ] = true;
                }
                if( s[ tp[i].y ]==false ) {
                    ans_tp ++;
                    s[ tp[i].y ] = true;
                }
                ans = max( ans,ans_tp );
            }
        }
        cout<<ans<<endl;
        //printf("%lld
",ans);
    }
    return 0;
}

 方法二：利用极角来排序 判断

/*
几何
极角排序
*/
#include<algorithm>  
#include<iostream>  
#include<string.h>  
#include<stdlib.h>  
#include<stdio.h>  
#include<math.h>  
#include<queue>  
#include<stack>  
#include<map>  
#include<set>  
using namespace std;  
typedef long long int64;  
//typedef __int64 int64;  
typedef pair<int64,int64> PII;  
#define MP(a,b) make_pair((a),(b))   
const int inf = 0x3f3f3f3f;  
const double inf2 = 987654321.0;
const double pi=acos(-1.0);  
const int dx[]={1,-1,0,0};  
const int dy[]={0,0,1,-1};  
const double eps = 1e-8;  
const int maxm = 1005;  
const int maxn = 705;  

struct Point{
    double x,y;
}pnt[ maxn ],pnt2[ maxn ];
Point C;

double td[ maxn ];

void initC( double x,double y ){
    C.x = x;
    C.y = y;
}

void initP( int n ){    
    for( int i=0;i<n;i++ ){
        pnt2[ i ].x = pnt[ i ].x - C.x;
        pnt2[ i ].y = pnt[ i ].y - C.y;
    }
    return ;
} 

void initTD( int n ){
    for( int i=0;i<n;i++ ){
        td[ i ] = atan2( pnt2[ i ].y,pnt2[ i ].x );
        if( td[i]<0 ) td[ i ] += pi;
        //printf("%.2lf ",td[i]);
    }
    //printf("
");
    sort( td,td+n );
    return ;
}

double dis( Point A,Point B ){
    A.x -= C.x,A.y -= C.y;
    B.x -= C.x,B.y -= B.y;
    return sqrt( (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y) );
}

double cmp( Point A,Point B ){
    double t1 = atan2( A.y-C.y,A.x-C.x );
    double t2 = atan2( B.y-C.y,B.x-C.x );
    if( t1<0 ){
        t1 = t1 + pi*2.0;
    }
    if( t2<0 ){
        t2 = t2 + pi*2.0;
    }
    if( t1==t2 ){
        return fabs( A.x )< fabs( B.x );
    }
    else{
        return t1<t2;
    }
}
/*******************************************
绕原点 以x正半轴开始逆时针旋转
角度相同 按距离原点距离比较 
*******************************************/

int main(){
    //freopen("in.txt","r",stdin);
    int n ;
    while( scanf("%d",&n)!=EOF ){
        for( int i=0;i<n;i++ ){
            scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
        }
        int ans = 0;
        double f = inf2;
        for( int i=0;i<n;i++ ){
            initC( pnt[ i ].x,pnt[ i ].y );
            initP( n );
            initTD( n );
            int cnt ;
            double pre = inf2;
            for( int j=0;j<n;j++ ){
                if( pre!=td[ j ] ){
                    pre = td[ j ];
                    cnt = 1;
                }
                else {
                    cnt ++;
                    if( cnt>ans ){
                        ans = cnt;
                        f = pre;
                    }
                    //ans = max( ans,cnt+1 );
                }
            }
        }
        if( f!=0 ) ans ++; 
        printf("%d
",max(2,ans));
    }
    return 0;
}