0

我正在尝试解决 spoj 上的 CLOPPAIR 问题，我必须找到两点之间的最小欧几里德距离并打印这两个点的索引。我尝试使用扫描线来做到这一点，但我仍然得到 TLE 。请有人帮助我吗？

这是我的代码 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;
}
4

1 回答 1

1

您的解决方案的时间复杂度是O(N^2)最坏的情况（例如，如果所有点都具有相同的 ，就会发生这种情况x）。这对于给定的约束来说太多了。

但是，可以修复您的解决方案。您应该将点按y-coordinate 排序在一个集合中，并且仅在按顺序进行的 for 循环内的集合的 [s.upper_bound(curY) - curBest, s.upper_bound(curY) + curBest) 范围内进行迭代x。这样，时间复杂度是O(N log N)最坏的情况。

于 2017-01-19T11:45:41.210 回答