c++ - 垂直扫动最接近的一对

如here所述，最接近对的标准扫掠线算法是众所周知的，它使用扫掠线水平扫过点集，仅将那些点保持在当前点的当前最佳距离内。

通常，点必须首先按x坐标排序，并且边界框(对于c++实现为std::set)必须按y坐标排序，如this c++ implementation所示。

但是，在尝试实现时，我意外地忘记了按x坐标对点进行排序，而是按y坐标对它们进行了排序。令人惊讶的是，这似乎仍然有效。
您可以看到我的实现here，它基本上遵循标准的线扫最接近对算法的稍微修改的版本:

#include <iostream>
#include <set>
#include <algorithm>
#include <math.h>
#include <vector>

using namespace std;

#define x second
#define y first

typedef pair<long long, long long> pll;

inline double dist(pll p1, pll p2)
{
    return sqrt((double) (p2.y - p1.y)*(p2.y - p1.y) + (p2.x - p1.x)*(p2.x - p1.x));
}


int main(int argc, const char * argv[])
{
    int numPoints;
    cin >> numPoints;

    vector <pll> points;
    points.resize(numPoints);

    for (int i = 0; i < numPoints; i++)
    {
        cin >> points[i].x >> points[i].y;
    }

    //Sorts the points by y coordinate (because y is first)
    sort(points.begin(), points.end());

    double shortestDistSoFar = INFINITY;
    set <pll> boundingBox; //Bounding box maintained by y-coordinate
    boundingBox.insert(points[0]);

    int left = 0;

    pll best1, best2;

    for (int i = 1; i < numPoints; i++)
    {
        //Maintain only points to the left of the current point whose distance is less than bestDist
        while ((left < i) && (points[i].x - points[left].x > shortestDistSoFar))
        {
            boundingBox.erase(points[left]);
            left++;
        }

        //Consider only points within bestDist of the current point
        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]);
    }

    return 0;
}

按增加y坐标的顺序访问每个点，并对每个点检查从y-bestDist到y + bestDist的所有点，在找到新的最短距离时更新bestDist，并从集合中删除与当前点的x坐标距离的点大于bestDist。

修改后的算法是否仍然有效(我仅在少数情况下进行了测试)，运行时间是否仍为O(N lgN)？

最佳答案

它确实可以正常工作(因为只有在可以安全删除点的情况下才将其从集合中删除)。但是，它具有O(n ^ 2)时间复杂性，因为在应该删除点时并不总是将其删除。

这个简单的生成器(用python3编写):

from sys import argv

n = int(argv[1])
dy = 1
dx = -n
print(n)
for i in range(n):
  print(dx * i, dy * i)

创建一个测试用例，使您的代码对任何O(n ^ 2)执行n操作。

这个测试用例的想法很简单:如果以x坐标的降序迭代这些点(按y坐标排序)，则它们永远不会从集合中删除。因此，如果它们通过y坐标彼此靠近，而通过x坐标彼此靠近，则每次都遍历整个集合。这就是为什么要检查所有成对的点(并且确实有n * (n - 1) / 2对)的原因。

现在让我们看看它如何在实践中起作用:
首先，我使用g++ -std=c++11 -O2 closest_pair.cpp编译了您的代码。
之后，我进行了一系列测试:

temp$ python3 gen.py 10000 > input
temp$ time ./a.out < input

real    0m0.805s
user    0m0.797s
sys     0m0.008s

temp$ python3 gen.py 30000 > input
temp$ time ./a.out < input

real    0m7.195s
user    0m7.198s
sys     0m0.004s

temp$ python3 gen.py 50000 > input
temp$ time ./a.out < input

real    0m23.711s
user    0m23.725s
sys     0m0.004s

如您所见，它的运行速度非常慢。