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

機能クロス（a、b、c）は、

Aが は、三角形A、B、Cの領域を署名さ

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

を以下の行列の行列式を求めるています。 行列式の符号は、3つの点が時計回りまたは反時計回りに向いているかどうかを示します。 see here for an explanation

はqq上の最低点と船体PPの片側によって形成される三角形は同じ側によって形成される三角形よりも小さい場合

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]) 

だから、チェック、のは、次のように書き換えてみようとqqから次に高い点。

はいの場合は、qqの次の点をqと選択して続行します。 -i.e. qを選択して、からの垂直距離qが最小になるように選択します。

これは局所的ppのすべての側面のためにこれを繰り返し、所定の側<p, p+1>ために最小化されたら。各ステップで、現在のの間の最小距離を保ちます。

これは幾分shaky 2つの凸包の間の最小間隔を見つける方法です。直感は、理解するのが簡単であるという意味で正しいです（概念はではありません。）、凸多角形の場合は非常に一般的で、非常に有用なさまざまな問題があります。しかし、私はこれがはるかに効率的で分かりやすい方法で書くことができると感じています。

、このような考え方の背後にある直感をうまくこの論文に示されている "Solving Geometric Problems with the Rotating Calipers" - コードのスニペットについて尋ねたときにトゥーサンG.