Во-первых, я читал об алгоритме скользящей линии для поиска ближайшей пары точек за время 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), но изменение его на этот нарушает алгоритм.
Может ли кто-нибудь помочь решить эти, казалось бы, несовместимые вещи?
