algorithm - 扫线算法

我试图解决spoj上的问题，其中我必须找到两点之间的最小欧几里得距离，并打印这两点的索引。我试着用清扫线做这个，但我还是得到了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;
}

最佳答案

在最坏的情况下，你的解决方案的时间复杂度（例如，如果所有的点都具有相同的O(N^2)），它就会发生。对于给定的约束条件来说，这太多了。
但是，有可能修复您的解决方案。您应该保持点按集合中的x-坐标排序，并且只在按y顺序进行的for循环内集合的[s.upper_bound（curY）-curBest，s.upper_bound（curY）+curBest）范围内迭代在最坏情况下，时间复杂度为x。

关于algorithm - 扫线算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41740067/