スワイプラインアルゴリズム

Question

私はspojでCLOPPAIR問題を解決しようとしています。私は2点間の最小真理値距離を求め、これらの2点の指数も表示する必要があります。私はsweeplineを使ってこれをやろうとしましたが、私はまだ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座標でソートされたポイントをセットに入れ、forループ内の[s.upper_bound（curY） - curBest、s.upper_bound（curY）+ curBest）の範囲内でのみ、xの順序で繰り返す必要があります。この方法では、最悪の場合、時間の複雑さはO(N log N)になります。