LA 4728 Square ，旋轉卡殼法求多邊形的直徑

LA 4728 Square ，旋轉卡殼法求多邊形的直徑

給出一些正方形，讓你求這些正方形頂點之間的最大距離的平方。

//返回點集直徑的平方
int diameter2(vector & points) {
    vector p = ConvexHull(points);
    int n = p.size();
    if(n==1) return 0;
    if(n==2) return Dist2(p[0], p[1]);
    p.push_back(p[0]);
    int ans = 0;
    for(int u = 0, v = 1; u < n; ++u) {
        for(;;) {
            int diff = Cross(p[u+1]-p[u], p[v+1]-p[v]);
            if(diff<=0) {
                ans = max(ans, Dist2(p[u], p[v]));
                if(diff==0) ans = max(ans, Dist2(p[u], p[v+1]));
                break;
            }
            v = (v+1) % n;
        }
    }
    return ans;
}