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.x a.y 1 | | b.x b.x 1 | = 2 * A | c.x c.y 1 | 

삼각형의 A, B, C의 영역 서명은 다음 행렬의 행렬식을 찾는 것이다. 결정자의 부호는 3 점이 시계 방향 또는 시계 반대 방향으로 향하고 있는지 알려줍니다. 삼각형은 qq에 최저 지점 선체 PP의 일측으로 형성하는 경우 이런 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]) 

그래서 동일한 측면에 의해 형성된 삼각형보다 작은 검사 qq에서 다음으로 높은 지점.

예 인 경우 qq의 다음 점을 q으로 선택하고 계속하십시오. - i.e. q을 선택하여 측면 <p, p+1>에서의 수직 거리 이 최소화되도록 선택하십시오. 한번

로컬 소정 측 <p, p+1> 위해 최소화된다 pp의 모든면에 대해이를 반복한다. 각 단계에서 사이의 최소 거리를 현재면 사이에 유지하십시오.

이것은 다소 흔들리는 두 개의 convexhull 사이의 최소 간격을 찾는 방법입니다. 직관은 이해하기 쉽다는 의미에서 정확하다. (개념은 이 아니고, 문제의 코드는) 볼록 다각형의 경우 매우 일반적이며 다양한 문제가 매우 유용하다 (아래 참고 자료 참조). 그러나 나는 이것이 훨씬 더 효율적이고 이해하기 쉬운 방법으로 쓰여질 수 있다고 생각한다. 코드 조각에 대해 물어 때