首页 > 代码库 > poj2780Linearity(多点共线)

poj2780Linearity(多点共线)

链接

判断最多多少点在一条直线上,

可以枚举每一个点为坐标系的原点,其它点变成相应的位置,然后求得过原点及其点的斜率,排序找一下最多相同的。

 1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 #include<map>11 using namespace std;12 #define N 101013 #define LL long long14 #define INF 0xfffffff15 const double eps = 1e-8;16 const double pi = acos(-1.0);17 const double inf = ~0u>>2;18 19 struct point20 {21     int x,y;22     point(int x=0,int y=0):x(x),y(y){}23 }p[N];24 double o[N];25 26 typedef point pointt;27 pointt operator -(point a,point b)28 {29     return point(a.x-b.x,a.y-b.y);30 }31 int dcmp(double x)32 {33     if(fabs(x)<eps) return x;34     return x<0?-1:1;35 }36 37 int main()38 {39     int n,i,j;40     while(scanf("%d",&n)!=EOF)41     {42         for(i = 1; i <= n; i++)43         {44             scanf("%d%d",&p[i].x,&p[i].y);45         }46         int maxz=0;47         for(i = 1; i <= n; i++)48         {49             int ans = 0 ,g=0;50             for(j = 1; j <= n ;j++)51             {52                 int x = p[j].x-p[i].x;53                 int y = p[j].y-p[i].y;54                 if(x==0)55                 ans++;56                 else o[g++] = y*1.0/x;57             }58             sort(o,o+g);59             int num = 2;60             for(j = 1; j < g; j++)61             if(dcmp(o[j]-o[j-1])==0)62             num++;63             else64             {ans = max(ans,num);65                 num = 2;66 67             }68             ans = max(ans,num);69             maxz = max(maxz,ans);70         }71         printf("%d\n",maxz);72     }73     return 0;74 }
View Code