Sweepline算法

Question

我想解決問題CLOPPAIR上的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; 
} 

Answer 1

解決方案的時間複雜度是在最壞情況下O(N^2)（例如，它發生，如果所有的點都相同x）。對於給定的約束條件，這太多了。

但是，可以修復您的解決方案。你應該保持在y -coordinate排序的點在一個集合中，並且迭代只在for循環中的集合的[s.upper_bound（curY） - curBest，s.upper_bound（curY）+ curBest）範圍內進行，該集合的範圍爲x 。這樣，在最壞的情況下，時間複雜度爲O(N log N)。