题意：给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 = ;
const int64 maxm = ;
const int64 inf = -;
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=;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=;i<n;i++ ){
cin>>pnt[i].x>>pnt[i].y;
//scanf("%lld%lld",&pnt[i].x,&pnt[i].y);
s[ i ] = false;
}
if( n==||n== ){
printf("%d\n",n);
continue;
}
int cnt = ;
for( int i=;i<n;i++ ){
for( int j=i+;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 = ;
int64 ans_tp = ;
int64 prea = inf;
int64 preb = inf;
int64 prec = inf;
for( int i=;i<cnt;i++ ){
if(( prea!=tp[ i ].a || preb!=tp[ i ].b || prec!=tp[ i ].c )){
ans_tp = ;
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\n",ans);
}
return ;
}
方法二：利用极角来排序 判断
/*
几何
极角排序
*/
#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[]={,-,,};
const int dy[]={,,,-};
const double eps = 1e-;
const int maxm = ;
const int maxn = ; 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=;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=;i<n;i++ ){
td[ i ] = atan2( pnt2[ i ].y,pnt2[ i ].x );
if( td[i]< ) td[ i ] += pi;
//printf("%.2lf ",td[i]);
}
//printf("\n");
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< ){
t1 = t1 + pi*2.0;
}
if( t2< ){
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=;i<n;i++ ){
scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
}
int ans = ;
double f = inf2;
for( int i=;i<n;i++ ){
initC( pnt[ i ].x,pnt[ i ].y );
initP( n );
initTD( n );
int cnt ;
double pre = inf2;
for( int j=;j<n;j++ ){
if( pre!=td[ j ] ){
pre = td[ j ];
cnt = ;
}
else {
cnt ++;
if( cnt>ans ){
ans = cnt;
f = pre;
}
//ans = max( ans,cnt+1 );
}
}
}
if( f!= ) ans ++;
printf("%d\n",max(,ans));
}
return ;
}