旋转卡壳

// p1452
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
#define I inline
#define R register
#define inf 1073742823
#define FOR(i,begin,end) for(R int i=begin;i<=end;++i)
#define ROF(i,begin,end) for(R int i=begin;i>=end;--i)

const int maxn = 200000+20;

const double eps=1e-10;
const double pi=acos(-1.0);
I int dcmp(double x)
{   if(fabs(x)<eps)return 0;
    else return x<0?-1:1;}
#define P point
#define PP const P &
struct point{
    double x,y;
    I P(const double &_x=0,const double &_y=0):x(_x),y(_y){}
    I bool operator ==(PP a)const{return dcmp(x-a.x)==0&&dcmp(y-a.y)==0;}
    I bool operator<(PP a)const{return x<a.x||(x==a.x&&y<a.y);}
    I P operator+(PP a)const{return P(x+a.x,y+a.y);}
    I P operator-(PP a)const{return P(x-a.x,y-a.y);}
    I P operator*(const double a)const{return P(x*a,y*a);}
    I P operator/(const double a)const{return P(x/a,y/a);}
    I P operator*(PP a)const{return P(x*a.x-y*a.y,x*a.y+y*a.x);}
    I double len()const{return sqrt(x*x+y*y);}
    I double len2()const{return x*x+y*y;}
    I P rotate(const double theta)const{return P(x,y)*P(cos(theta),sin(theta));}
    I double operator|(PP a)const{return x*a.x+y*a.y;}
    I double operator&(PP a)const{return x*a.y-y*a.x;}
    I P norm(){return *this/len();}
    I double angle(PP a)const{return *this|a/len()/a.len();}
}p[maxn],s[maxn];
int n,top;
typedef point vec;

I bool cmp(PP a,PP b){
    vec p1=a-p[1],p2=b-p[1];
    double k=(p1)&(p2);
    if(dcmp(k)==1)return 1;
    if(dcmp(k)==0&&p1.len2()<p2.len2())return 1;
    return 0;
}

signed main(){
    scanf("%d",&n);
    FOR(i,1,n){
        scanf("%lf%lf",&p[i].x,&p[i].y);
        if(p[i]<p[1])swap(p[1],p[i]);
    }
    sort(p+2,p+1+n,cmp);
    s[top=1]=p[1];
    FOR(i,2,n){
        while(top>1&&(dcmp((s[top]-s[top-1])&(p[i]-s[top])))<=0)top--;
        s[++top]=p[i];
    }
    s[0]=s[top];
    int j=2;
    double ans=0;
    for(int i=0;i<top;++i){
        while(((s[i + 1] - s[i]) & (s[j] - s[i])) < ((s[i + 1] - s[i]) & (s[j + 1] - s[i])))j=(j+1)%n;
        ans=max(ans, max((s[i+1]-s[j]).len2(),(s[i]-s[j]).len2()));
    }
    printf("%d",(int)ans);
    return 0;
}