Gym - 101635K：Blowing Candles （简单旋转卡壳，求凸包宽度）

#include#define ll long long
#define rep(i,a,b) for(int i=a;i#define RC rotating_calipers
using namespace std;
const int maxn=400010;
struct point{
    ll x,y;
    point(double x=0,double y=0):x(x),y(y){}
    bool operator const point &c) const { return xc.y);}
    point operator - (const point &c) const { return point(x-c.x,y-c.y);}
};
ll det(point A,point B){ return A.x*B.y-A.y*B.x;}
ll det(point O,point A,point B){ return det(A-O,B-O);}
point a[maxn],ch[maxn];
void convexhull(int n,int &top)
{
    sort(a+1,a+n+1); top=0;
    for(int i=1;i){
        while(top>1&&det(ch[top-1],ch[top],a[i])0) top--;
        ch[++top]=a[i];
    }
    int ttop=top;
    for(int i=n-1;i>=1;i--){
        while(top>ttop&&det(ch[top-1],ch[top],a[i])0) top--;
        ch[++top]=a[i];
    }
}
double rotating_calipers(point p[],int top)
{
    double ans=123456789009876; int now=2;
    rep(i,1,top-1){
        while(abs(det(p[i],p[i+1],p[now]))1],p[now+1]))){
            now++; if(now==top) now=1;
        }
        double tmp=fabs(1.0*det(p[i],p[i+1],p[now]));
        tmp/=sqrt(1.0*(p[i].x-p[i+1].x)*(p[i].x-p[i+1].x)+(p[i].y-p[i+1].y)*(p[i].y-p[i+1].y));
        ans=min(ans,tmp);
    }
    return ans;
}
int main()
{
    int N; double S; scanf("%d%lf",&N,&S);
    for(int i=1;i"%I64d%I64d",&a[i].x,&a[i].y);
    int top; convexhull(N,top);
    printf("%.15lf\n",RC(ch,top));
    return 0;
}