学步园

poj 3608 Bridge Across Islands

求两个凸包的最小距离。

旋转卡壳求凸多边形间最小距离   点击打开链接

double Rotating_Calipers_Distance(vector<Point>& ch1, vector<Point>& ch2){
    vector<Point> P = ConvexHull(ch1);
    vector<Point> Q = ConvexHull(ch2);
    int n = P.size(), m = Q.size();
    int yminP = 0, ymaxQ = 0;
    for(int i=0; i<n; ++i)
        if(P[i].y <P[yminP].y)
            yminP = i;
    for(int i=0; i<m; ++i)
        if(Q[i].y>Q[ymaxQ].y)
            ymaxQ = i;
    P.push_back(P[0]);
    Q.push_back(Q[0]);
    double tmp, ans = 1e20;
    for(int i=0; i<n; ++i)
    {
//Cross(Q[ymaxQ+1],P[yminP],P[yminP+1]) - Cross(Q[ymaxQ],P[yminP],P[yminP+1])
        while( tmp=Cross(Q[ymaxQ+1]-Q[ymaxQ], P[yminP]-P[yminP+1]) > eps)
            ymaxQ = (ymaxQ+1) % m;
        if(tmp <-eps) ans = min(ans, DistanceToSegment(Q[ymaxQ], P[yminP], P[yminP+1]));
        else ans = min(ans, DistanceTwoSegment(P[yminP],P[yminP+1], Q[ymaxQ],Q[ymaxQ+1]));
        yminP = (yminP+1) % n;
    }
    return ans;
}