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-;
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 = ;while(!isdigit(c)) c = getchar();
while(isdigit(c)) { x = x * + c - ''; c = getchar(); }
} const int maxn=;
int n,ans;
struct X{LL x,y;}s[maxn],t[maxn]; LL gcd(LL a,LL b)
{
if(b==) 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<) a=-a;
return a;
} int main()
{
while(~scanf("%d",&n))
{
if(n==) break; ans=;
for(int i=;i<=n;i++) scanf("%lld%lld",&s[i].x,&s[i].y);
sort(s+,s++n,cmp);
for(int i=;i<=n;i++)
{
int sz=;
for(int j=i+;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==) continue;
sort(t,t+sz,cmp); int k=;
for(int i=;i<sz;i++)
{
if(t[i].x==t[i-].x&&t[i].y==t[i-].y) k++;
else ans=max(ans,k+),k=;
}
ans=max(ans,k+);
}
printf("%d\n",ans);
}
return ;
}
上一篇:全站最硬核 百万字强肝RocketMq源码 火热更新中~(八十六)延时队列


下一篇:【模板】Sparse-Table