• https://oi-wiki.org/geometry/rotating-calipers/
• https://www.luogu.com.cn/problem/P1452 | https://vjudge.net/problem/POJ-2187
  直径
• https://www.luogu.com.cn/problem/P3187
  最小矩形覆盖
• https://vjudge.net/problem/Gym-101175K
  最小矩形覆盖、凸包宽度
• https://codeforces.com/contest/1578/problem/F
  最小矩形覆盖 + 微积分
• https://vjudge.net/problem/POJ-3608
  凸包间距

#include <lastweapon/geometry>
using namespace lastweapon;
using namespace CG;

typedef vector<Po> VP;

#define suc(x) (x+1==n?0:x+1)
DB rc(const VP& P){
    int n = SZ(P)-1, j = 1; DB d2 = 0; REP(i, n){
        while (dett(P[i+1]-P[i], P[j+1]-P[j])>0) j=suc(j);
        checkMax(d2, max(dist2(P[i], P[j]), dist2(P[i+1], P[j])));
    }
    return d2;
}

VP P; int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); P.resize(n); REP(i, n) P[i].in();
    printf("%.0f\n", rc(getCH(P)));
}

Posted by xiaodao
Category: 日常