Понимание конкретной реализации линии свипирования ближайшей пары

Question

Во-первых, я читал об алгоритме линии развертки, чтобы найти ближайшую пару точек за O(N lgN) в верхнем кодере. Я в основном понимал алгоритм, однако, когда я смотрю на реализацию, представленную здесь (скопированную и сделанную более читабельной ниже), я замечаю некоторые поразительные различия.

#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]);
}

Во-первых, в приведенном выше фрагменте реализации std::set, который содержит точки и представляет ограничивающий прямоугольник, не сортируется по 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 является первым элементом пары. Поэтому точки в наборе упорядочены правильно.