旋转卡壳求凸包直径

思路

直径即最长的两点的距离
枚举凸包上的所有边，对每一条边找出凸包上离该边最远的顶点（用叉积），计算这个顶点到该边两个端点的距离，并记录最大的值。但是注意到当我们逆时针枚举边的时候，最远点的变化也是逆时针的，这样就可以不用从头计算最远点，而可以紧接着上一次的最远点继续计算。于是我们得到了O(n)的算法。

复制的图

---

常数巨大的丑陋代码

# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# include <math.h>
# include <algorithm>
# define RG register
# define IL inline
# define ll long long
# define mem(a, b) memset(a, b, sizeof(a))
# define Min(a, b) (((a) > (b)) ? (b) : (a))
# define Max(a, b) (((a) < (b)) ? (b) : (a))
# define Sqr(a) ((a) * (a))
using namespace std;

const int MAXN = 50001;
int n, top = 2;
struct Point{
    int x, y, len;
} p[MAXN], Point_A, s[MAXN]; //最左下的点 
//求叉积(向量ab，向量ac) 
IL int Cross(Point a, Point b, Point c){
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
//极角排序 
IL int Dis(Point a, Point b){
    return Sqr(a.x - b.x) + Sqr(a.y - b.y);
}

IL bool Cmp(Point a, Point b){
    RG int x = Cross(Point_A, a, b);
    if(x > 0) return 1;
    else if(x < 0) return 0;
    a.len = Dis(Point_A, a);
    b.len = Dis(Point_A, b);
    return a.len < b.len;
}

IL void Find(){
    Point_A = p[1]; RG int temp = 0;
    for(RG int i = 2; i <= n; i++)
        if((Point_A.y == p[i].y && Point_A.x > p[i].x) || Point_A.y > p[i].y)
            Point_A = p[i], temp = i;
    p[temp] = p[1]; p[1] = Point_A;
}

IL void Graham(){
    Find();
    sort(p + 2, p + n + 1, Cmp);
    p[++n] = s[0] = p[1]; s[1] = p[2]; s[2] = p[3];
    for(RG int i = 4; i < n; i++){
        while(Cross(s[top - 1], s[top], p[i]) <= 0 && top) top--;
        s[++top] = p[i];
    }
    s[++top] = p[n];
}

IL int Rot_Cover(){
    RG int q = 1, ans = 0;
    for(RG int i = 0; i < top; i++){
        while(Cross(s[i], s[i + 1], s[q]) < Cross(s[i], s[i + 1], s[q + 1])) q = (q + 1) % top;
        //等底的情况下,叉积越大即面积越大离该点越远 
        ans = Max(ans, Dis(s[i], s[q]));
        ans = Max(ans, Dis(s[i + 1], s[q]));
        //判断边平行的情况 
    }
    return ans;
}

int main(){
    scanf("%d", &n);
    for(RG int i = 1; i <= n; i++)
        scanf("%d%d", &p[i].x, &p[i].y);
    if(n == 2) return !printf("%d
", Dis(p[1], p[2]));
    Graham();
    printf("%d
", Rot_Cover());
    return 0;
}

裸题 Beauty Contest POJ - 2187