首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。