POJ2187 Beauty Contest

问题分析

求平面最远点对。凸包+旋转卡壳。

WA了5发是因为自作聪明认为找对踵点可以直接看两个点，保持距离最大……然后被下面这组数据叉掉了……

input:
10
0 0
10000 0
1 100
2 199
9999 100
9998 199
100 -900
200 -1799
9800 -1799
9900 -900

output:
100000000

所以还是老老实实地写吧……

参考程序

有压行嫌疑

#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
const LL Maxn=50010;
struct point{
    LL x, y;
    point(){}
    point(LL _x, LL _y):x(_x),y(_y){}
    inline point operator -(const point Other)const{return point(x-Other.x, y-Other.y); }
    inline LL operator *(const point Other)const{return x*Other.y-Other.x*y;}
};
LL N, Size;
point A[Maxn], Stack[Maxn];
inline LL Dis(point x,point y){return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);}
inline bool Cmp1(point x,point y){return x.y<y.y||(x.y==y.y&&x.x<y.x);}
inline bool Cmp2(point x,point y){return (x-A[1])*(y-A[1])>0||((x-A[1])*(y-A[1])==0&&Dis(x,A[1])<Dis(y,A[1]));}
int main(){
    scanf("%lld",&N);
    for(LL i=1;i<=N;++i) scanf("%lld%lld",&A[i].x,&A[i].y);
    std::sort(A+1,A+N+1,Cmp1);
    std::sort(A+2,A+N+1,Cmp2);
    Stack[++Size]=A[1];
    for(LL i=2;i<=N;++i){
        for(;Size>1&&(A[i]-Stack[Size-1])*(Stack[Size]-Stack[Size-1])>=0;--Size);
        Stack[++Size]=A[i];
    }
    LL T=1,Nxt=2;
    for(;(Stack[1]-Stack[Size])*(Stack[Nxt]-Stack[T])>0;T=Nxt,Nxt=(T+1>Size)?1:T+1);
    LL Ans=Dis(Stack[Size],Stack[T]);
    for(LL i=1;i<Size;++i){
        for(;(Stack[i+1]-Stack[i])*(Stack[Nxt]-Stack[T])>0;T=Nxt,Nxt=(T+1>Size)?1:T+1);
        Ans=std::max(Ans,Dis(Stack[T],Stack[i]));
    }
    printf("%lld\n",Ans);
    return 0;
}