c++ - 看不懂HDU 2823的解决办法

Question

以下代码片段取自 here 。就是这个问题HDU 2823的解决方案。

#define eps 1e-9
double rc(point pp[],point qq[],int n,int m)    
{    
    int q=0;    
    int p=0;    
    for(int i=0;i<n;i++)     
        if(pp[i].y-pp[p].y<-eps)    
            p=i;    
    for(int i=0;i<m;i++)    
        if(qq[i].y-qq[q].y>eps)    
            q=i;    
    pp[n]=pp[0];    
    qq[m]=qq[0];    
    double tmp,ans=1e99;    
    for(int i=0;i<n;i++)    
    {    
        while((tmp=cross(pp[p+1],qq[q+1],pp[p])-cross(pp[p+1],qq[q],pp[p]))>eps)    
            q=(q+1)%m;    
        if(tmp<-eps)    
            ans=min(ans,dist_p_to_seg(qq[q],pp[p],pp[p+1]));    
        else    
            ans=min(ans,dist_seg_to_seg(pp[p],pp[p+1],qq[q],qq[q+1]));    
        p=(p+1)%n;    
    }    
    return ans;    

}    

pp[] 和qq[] 是两个不同的凸包。 p是pp凸包的最高点，q是qq凸包的最低点。

我似乎无法理解这一行:

while((tmp=cross(pp[p+1],qq[q+1],pp[p])-cross(pp[p+1],qq[q],pp[p]))>eps) 
    q=(q+1)%m;

他想达到什么目的？

Answer 1

函数 cross(a, b, c) 正在寻找以下矩阵的行列式，

| a.x a.y 1 |
| b.x b.x 1 |  = 2 * A
| c.x c.y 1 | 

其中 A 是三角形 a、b、c 的signed 面积。行列式的符号也告诉我们 3 个点是顺时针还是逆时针。 see here for an explanation

让我们这样重写，

triA ← cross(pp[p+1],qq[q+1],pp[p])
triB ← cross(pp[p+1],qq[q],pp[p])

// This is equivalent to,
// just to make it a bit clearer
triA ← cross(pp[p], pp[p+1],    qq[q+1])
triB ← cross(pp[p], pp[p+1],    qq[q])

因此它检查由船体 pp 的一侧形成的三角形是否具有 qq 上的最低点小于由qq的同边和下一个最高点组成的三角形。

如果是，则选择qq中的下一个点为q并继续。 -IE。选择 q使得 q 的垂直距离从侧面<p, p+1>被最小化。

一旦对给定的边进行了局部最小化 <p, p+1> ，对 pp 的所有边重复此操作.在每一步都保持当前边之间的最小距离。

这是一种寻找两个凸包之间最小间隔的不稳定方法。直觉是正确的——正确的是它易于理解(想法，不是有问题的代码)，对于凸多边形非常通用，并且对各种问题都非常有用(请参阅引用资料以下);但是，我觉得可以用一种更有效、更易于理解的方式来编写。

这篇论文很好地说明了这些想法背后的直觉 "Solving Geometric Problems with the Rotating Calipers"-- 图森特 G.