c++ - スイープ ラインの最も近いペアの特定の実装について理解する

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 は、(x 座標ではなく) y 座標によって並べ替えられていません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)これに変更するとアルゴリズムが壊れます。

誰かがこれらの一見矛盾したことに対処するのを手伝ってくれませんか?