首页 > 代码库 > POJ 1118 Lining Up
POJ 1118 Lining Up
枚举,排序。
先将所有点按双关键字排序,然后枚举线的顶点$P$,剩余的点以$P$为中心进行极角排序,可以取个$gcd$,这样一样的点就排在一起了,然后统计一下更新答案。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}const int maxn=800;int n,ans;struct X{LL x,y;}s[maxn],t[maxn];LL gcd(LL a,LL b){ if(b==0) return a; return gcd(b,a%b);}bool cmp(X a,X b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x;}LL ABS(LL a){ if(a<0) a=-a; return a;}int main(){ while(~scanf("%d",&n)) { if(n==0) break; ans=1; for(int i=1;i<=n;i++) scanf("%lld%lld",&s[i].x,&s[i].y); sort(s+1,s+1+n,cmp); for(int i=1;i<=n;i++) { int sz=0; for(int j=i+1;j<=n;j++) { t[sz].x=s[j].x-s[i].x; t[sz].y=s[j].y-s[i].y; LL GCD=gcd(ABS(t[sz].x),ABS(t[sz].y)); t[sz].x=t[sz].x/GCD; t[sz].y=t[sz].y/GCD; sz++; } if(sz==0) continue; sort(t,t+sz,cmp); int k=1; for(int i=1;i<sz;i++) { if(t[i].x==t[i-1].x&&t[i].y==t[i-1].y) k++; else ans=max(ans,k+1),k=1; } ans=max(ans,k+1); } printf("%d\n",ans); } return 0;}
POJ 1118 Lining Up
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。