Алгоритм Sweepline

Question

Я пытаюсь решить проблему CLOPPAIR на spoj, в которой я должен найти минимальное эвклидовое расстояние между двумя точками и напечатать индексы этих двух точек. Я попытался сделать это с помощью 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 -координате в наборе и итерации только по диапазону [s.upper_bound (curY) - curBest, s.upper_bound (curY) + curBest) набора внутри цикла for, который идет в x порядке , Таким образом, временная сложность O(N log N) в худшем случае.