스윕 라인 가장 가까운 쌍의 특정 구현 이해

Question

먼저, 스위프 라인 알고리즘에 대해 가장 가까운 쌍의 점을 O (N lgN) 시간에 찾아서 topcoder에 대해 읽었습니다. 나는 대부분 알고리즘을 이해하지만, 구현을 보면 here (복사하고 아래에서 더 읽을 수있게 만들었습니다.), 나는 눈에 띄는 차이점을 발견했습니다.

#define x first 
#define y second 
typedef pair<long long, long long> pll; 
    ... 
set <pll> boundingBox; 
boundingBox.insert(points[0]); //Points have been already sorted by x-coordinate 
for (int i = 1; i < numPoints; i++) 
{ 
    while ((left < i) && (points[i].x - points[left].x > shortestDistSoFar)) 
    { 
     boundingBox.erase(points[left]); 
     left++; 
    } 

    for (auto it = boundingBox.lower_bound(pll(points[i].y - shortestDistSoFar, points[i].x - shortestDistSoFar)); it != boundingBox.end() && it->y <= points[i].y + shortestDistSoFar; it++) 
    { 
     if (dist(*it, points[i]) < shortestDistSoFar) 
     { 
      shortestDistSoFar = dist(*it, points[i]); 
      best1 = *it; 
      best2 = points[i]; 
     } 
    } 
    boundingBox.insert(points[i]); 
} 

먼저, 위의 구현 코드에서, 포인트를 보유하고 경계 사각형을 나타내는 표준 : 집합으로 분류되지 않는 y 좌표 (대신하여 x 좌표) 어떻게 거의 모든 반대되는 다른 출처 : The set is ordered by y coordinate. (Topcoder).

다음으로 집합이 y 좌표로 정렬되어 있지 않더라도 이터레이터를 consider points in the active set ... whose y coordinates are in the range yN − h to yN + h으로 사용하면 pll(points[i].y - shortestDistSoFar, points[i].x - shortestDistSoFar)의 하한으로 간주됩니다. y이 먼저 오는 이유는 무엇입니까? 나는 정확한 순서가 pll(points[i].x, points[i].y - shortestDistSoFar) 일 것이라고 생각할 것이다. 그러나 이것으로 바꾸면 알고리즘이 깨진다.

누군가가 이러한 겉으로보기에는 일관성없는 문제를 해결할 수 있습니까?

Answer 1

원래 코드에서 y 좌표는 쌍의 첫 번째 요소입니다. 그래서 집합의 점들이 올바르게 정렬됩니다.