扫描线算法

Question

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

#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)。

扫描线算法

Sweepline algorithm

algorithm

computational-geometry

closest-points