algorithm - 扫描线算法

Question

我正在尝试解决 spoj 上的 CLOPPAIR 问题，其中我必须找到两点之间的最小欧几里得距离，并打印这两个点的索引。我尝试使用扫描线执行此操作，但我仍然收到 T.L.E。有人可以帮助我吗？

这是我的代码 http://ideone.com/Tzy5Au

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class node{
    public:
    int idx;
    int x;
    int y;
    node(int xx=0,int yy=0,int ii=0){
        idx=ii;
        x=xx;
        y=yy;
    }
    friend bool operator<(node a,node b);
};
bool operator<(node a,node b){
    return(a.y<b.y);
}
bool cmp_fn(node a,node b){
    return(a.x<b.x);
}
void solve(node pts[],int n){
    int start,last;
    int left =0;
    double best=1000000000,v;
    sort(pts,pts+n,cmp_fn);
    set<node>box;
    box.insert(pts[0]);
    for(int i=1;i<n;i++){
        while(left<i && pts[i].x-pts[left].x >best){
            box.erase(pts[i]);
            left++;
        }
        for(typeof(box.begin())it=box.begin();it!=box.end() && pts[i].y+best>=it->y;it++){
            v=sqrt(pow(pts[i].y - it->y, 2.0)+pow(pts[i].x - it->x, 2.0));
            if(v<best){
                best=v;
                start=it->idx;
                last=pts[i].idx;
                if(start>last)swap(start,last);
            }
        }
        box.insert(pts[i]);
    }
    cout<<start<<" "<<last<<" "<<setprecision(6)<<fixed<<best;
} 
int main(){
    int t,n,x,y;
    cin>>n;
    node pts[n];
    for(int i=0;i<n;i++){
        cin>>x>>y;
        pts[i]=node(x,y,i);
    }
    solve(pts,n);
    return 0;
}

Answer 1

在最坏的情况下，您的解决方案的时间复杂度为 O(N^2)(例如，如果所有点都具有相同的 x)。对于给定的约束，这太多了。

但是，可以修复您的解决方案。您应该在集合中保持按 y 坐标排序的点，并仅在集合中的 [s.upper_bound(curY) - curBest, s.upper_bound(curY) + curBest) 范围内迭代按 x 顺序进行的 for 循环。这样，最坏情况下的时间复杂度为 O(N log N)。