Please help,为什么wa2个点啊,,,跟白书一个思路啊

P1429 平面最近点对(加强版)

LonelinessMan @ 2018-12-13 19:09:21

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef pair<db,db> P;
const int maxn=200010;
const db inf=1E200;
P a[maxn];
int n;
inline db dis(db x1,db y1,db x2,db y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
db solve(int l,int r){
    if(l==r)return inf;
    int mid=(l+r)>>1;
    db ret=min(solve(l,mid),solve(mid+1,r)),m=a[mid].first;
    int t1=l,t2=mid+1,t=0;
    vector<P>v,vt;
    while(t1<=mid&&t2<=r){
        if(a[t1].second<a[t2].second)v.push_back(a[t1]),++t1;
        else v.push_back(a[t2]),++t2;
    }
    while(t1<=mid)v.push_back(a[t1]),++t1;
    while(t2<=r)v.push_back(a[t2]),++t2;
    for(int i=0;i<v.size();++i)a[l+i]=v[i];
    for(int i=l;i<=r;++i){
        if(fabs(a[i].first-m)>=ret)continue;
        for(int j=vt.size()-1;j>=0;--j){
            if(fabs(vt[j].second-a[i].second)>=ret)continue;
            ret=min(ret,dis(a[i].first,a[i].second,vt[j].first,vt[j].second));  
        }
        vt.push_back(a[i]);
    }
    return ret;
}
int main(){
    freopen("a.txt","r",stdin);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i].first>>a[i].second;
    sort(a+1,a+1+n);
    printf("%.4lf",solve(1,n));
    return 0;
}

by LonelinessMan @ 2018-12-13 19:13:58

而且我的答案是偏小的。。。


by LonelinessMan @ 2018-12-13 19:30:41

我的答案是偏大的。。。说错了 if(fabs(a[i].first-m)>=ret)continue;删了就对了为什么啊


by LonelinessMan @ 2018-12-13 20:07:21

为什么把solve(l,mid)改成solve(l,mid-1)就对了。。


by w_II_j @ 2022-08-12 20:25:24

同...


|