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));
的前面