洛谷 P1452 Beauty Contest

题目背景

此处省略1W字^ ^

题目描述

贝茜在牛的选美比赛中赢得了冠军”牛世界小姐”。因此,贝西会参观N(2 < = N < = 50000)个农场来传播善意。世界将被表示成一个二维平面,每个农场位于一对整数坐标(x,y),各有一个值范围在-10000…10000。没有两个农场共享相同的一对坐标。

尽管贝西沿直线前往下一个农场，但牧场之间的距离可能很大,所以她需要一个手提箱保证在每一段旅程中她有足够吃的食物。她想确定她可能需要旅行的最大可能距离,她要知道她必须带的手提箱的大小。帮助贝西计算农场的最大距离。

输入输出格式

输入格式：

第一行：一个整数n

第2~n+1行：xi yi 表示n个农场中第i个的坐标

输出格式：

一行：最远距离的[b]平方[/b]

输入输出样例

输入样例#1：

输出样例#1：

说明

NONE

旋转卡壳模板题，求个凸包之后用叉积求出离当期枚举直线的最远点(肯定是单调变化的)

/*
    排序一定要严格按x第一关键字，y第二关键字升序排序，，，
    不然后果就是WA一墙调半天不知道哪错的hhhh 
*/
#include<bits/stdc++.h>
#define ll long long
#define maxn 50005
using namespace std;
const double eps=0.000000001;

inline int zt(double x){
    if(fabs(x)<=eps) return 0;
    return (x>0?1:-1);
}

inline double sq(double x){
    return x*x;
}

struct node{
    double x,y;
    
    node operator +(const node& u)const{
        return (node){x+u.x,y+u.y};
    }
    
    node operator -(const node& u)const{
        return (node){x-u.x,y-u.y};
    }
    
    node operator *(const double& u)const{
        return (node){x*u,y*u};
    }
    
    bool operator <(const node& u)const{
        return zt(x-u.x)?zt(x-u.x)<0:zt(y-u.y)<0;
    }
}a[maxn],q[maxn],ret[maxn];

inline double ptmul(node x,node y){
    return x.x*y.x+x.y*y.y;
}

inline double Xmul(node x,node y){
    return x.x*y.y-x.y*y.x;
}

inline bool eq(node x,node y){
    return (!zt(x.x-y.x)&&!zt(x.y-y.y));
}

inline double dist(node x,node y){
    return sq(x.x-y.x)+sq(x.y-y.y);
}

inline int get_hill(node *u,int len){
    sort(u+1,u+len+1);
    
    int tt=2,tot=0;
    q[1]=u[1],q[2]=u[2];
    for(int i=3;i<=len;i++){
        while(tt>1&&zt(Xmul(q[tt]-q[tt-1],u[i]-q[tt]))<0) tt--;
        q[++tt]=u[i];
    }
    for(int i=1;i<=tt;i++) ret[++tot]=q[i];
    
    tt=2;
    q[1]=u[1],q[2]=u[2];
    for(int i=3;i<=len;i++){
        while(tt>1&&zt(Xmul(q[tt]-q[tt-1],u[i]-q[tt]))>0) tt--;
        q[++tt]=u[i];
    }    
    int pre=tot;
    for(int i=tt;i;i--) if(!eq(q[i],ret[1])&&!eq(q[i],ret[pre])) ret[++tot]=q[i];
    
    for(int i=1;i<=tot;i++) u[i]=ret[i];
    return tot;
}

int n;
double ans=0;

inline void solve(){
    node r=a[1]-a[n];
    int pt=1,nxt=2;
    
    while(zt(fabs(Xmul(r,a[nxt]-a[n]))-fabs(Xmul(r,a[pt]-a[n])))>0){
        pt=nxt,nxt++;
        if(nxt>n) nxt-=n;
    }
    ans=max(ans,max(dist(a[1],a[pt]),dist(a[n],a[pt])));

    for(int i=1;i<n;i++){
        r=a[i+1]-a[i];
        while(zt(fabs(Xmul(r,a[nxt]-a[i]))-fabs(Xmul(r,a[pt]-a[i])))>0){
            pt=nxt,nxt++;
            if(nxt>n) nxt-=n;
        }
        ans=max(ans,max(dist(a[i],a[pt]),dist(a[i+1],a[pt])));
    }
    
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
    
    n=get_hill(a,n);

    solve();
    
    printf("%.0lf
",ans);
    return 0;
}