Sweepline 알고리즘

Question

나는 두 점 사이의 최소 유클리드 거리를 찾고이 두 점의 인덱스도 인쇄해야하는 spoj에서 CLOPPAIR 문제를 해결하려고합니다. 스위프 라인을 사용하여이 작업을 시도했지만 여전히 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 좌표로 정렬 된 점을 유지하고 x 순서로있는 for 루프 내부 집합의 [s.upper_bound (curY) - curBest, s.upper_bound (curY) + curBest) 범위에서만 반복합니다. . 이 방법은 최악의 경우 시간 복잡도가 O(N log N)입니다.