首页 > 代码库 > LA 4728 Square ,旋转卡壳法求多边形的直径

LA 4728 Square ,旋转卡壳法求多边形的直径

给出一些正方形,让你求这些正方形顶点之间的最大距离的平方。



//返回点集直径的平方
int diameter2(vector<Point> & points) {
    vector<Point> 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;
}