0

首先，我正在阅读有关扫描线算法的信息，以在 O(N lgN) 时间内找到最接近的点对topcoder。我主要了解该算法，但是当我查看此处提供的实现（复制并在下面更易读）时，我注意到一些显着的差异。

#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)但是将其更改为这会破坏算法。

有人可以帮助解决这些看似不一致的事情吗？

4

1 回答 1

1

在原始代码中，y 坐标是一对的第一个元素。这就是为什么集合中的点被正确排序的原因。

于 2014-12-28T09:34:11.227 回答