首页 > 代码库 > 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