想问一下我这个分治为什么143?

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

wanghai673 @ 2021-12-28 21:07:07

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define pb push_back
#define fir first
#define sec second
#define db(x) cerr<<#x<<":"<<x<<endl;
void pr() {cout<<endl;}
template<typename T1,typename... T2>
void pr(const T1& arg,const T2&... args){
    cout<<arg<<" ";
    pr(args...);
}
ll qm(ll a,ll b,ll MOD){ll ret = 1;assert(b>=0);while(b){if(b&1)ret=ret*a%MOD;b>>=1;a=a*a%MOD;}return ret;}
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}

const ll inf = 1e18;
const int N = 4e5 + 10;
struct points{
    int x,y;
    bool operator <(const points& b){
        return x<b.x; 
    }
}p[N],tmp[N];
inline ll dis(points a,points b){
    ll dx = (a.x-b.x),dy = a.y-b.y;
    return dx*dx+dy*dy; 
}
ll solve(int l,int r){
    if(l>=r)return inf;
    int m = (l+r)>>1;
    ll d = min(solve(l,m),solve(m+1,r));
    double td = sqrt(d);
    int k = 0,i = l,j = m+1,m_x = p[m].x;
    while(i<=m&&j<=r){
        if(p[i].y>p[j].y)tmp[++k] = p[i++];
        else tmp[++k] = p[j++];
    }
    while(i<=m)tmp[++k]=p[i++];
    while(j<=r)tmp[++k]=p[j++];
    for(int i = l;i<=r;++i){
        p[i] = tmp[i-l+1];
    }

    k = 0;
    for(int i = l;i<=r;++i){
        if(p[i].x-m_x<=td&&m_x-p[i].x<=td){
            tmp[++k] = p[i];
        }
    }

    for(int i = 1;i<=k;++i){
        for(int j = i-1;j>=1&&tmp[j].y-tmp[i].y<=td;--j){
            d = min(d,dis(tmp[i],tmp[j]));
        }
    }
    return d;
}
int main(){
    //freopen("a.txt","r",stdin);
    IOS;
    int n;
    cin>>n;
    for(int i = 1;i<=n;++i){
        cin>>p[i].x>>p[i].y;
    }
    sort(p+1,p+1+n);
    cout<<solve(1,n);

    return 0;

}

by wanghai673 @ 2021-12-28 21:12:51

why???0.0难道是精度啥问题 还是min的问题


by The_Last_Candy @ 2022-08-22 19:55:42

2022年,前来做题&考古的蒟蒻发现了这个问题:

int k = 0,i = l,j = m+1,m_x = p[m].x;

这一句中m_x = p[m].x;这句话放在了二分函数后面,此时l到mid区间早已被按照y值排序,这个m_x也就不是区间的中间x值了。 可以将此句放在

ll d = min(solve(l,m),solve(m+1,r));

的前面


|