poj2780Linearity(多点共线）

链接

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

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

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 using namespace std;

 #define N 1010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 struct point

 {

     int x,y;

     point(int x=,int y=):x(x),y(y){}

 }p[N];

 double o[N];

 typedef point pointt;

 pointt operator -(point a,point b)

 {

     return point(a.x-b.x,a.y-b.y);

 }

 int dcmp(double x)

 {

     if(fabs(x)<eps) return x;

     return x<?-:;

 }

 int main()

 {

     int n,i,j;

     while(scanf("%d",&n)!=EOF)

     {

         for(i = ; i <= n; i++)

         {

             scanf("%d%d",&p[i].x,&p[i].y);

         }

         int maxz=;

         for(i = ; i <= n; i++)

         {

             int ans =  ,g=;

             for(j = ; j <= n ;j++)

             {

                 int x = p[j].x-p[i].x;

                 int y = p[j].y-p[i].y;

                 if(x==)

                 ans++;

                 else o[g++] = y*1.0/x;

             }

             sort(o,o+g);

             int num = ;

             for(j = ; j < g; j++)

             if(dcmp(o[j]-o[j-])==)

             num++;

             else

             {ans = max(ans,num);

                 num = ;

             }

             ans = max(ans,num);

             maxz = max(maxz,ans);

         }

         printf("%d\n",maxz);

     }

     return ;

 }