没人发???
2025-02-23 15:20:23
发布于:江苏
10阅读
0回复
0点赞
#include<bits/stdc++.h> //万能头棒棒哒
//#include<windows.h>
//#include<conio.h>
#define lc t[p].l
#define rc t[p].r
using namespace std;
const int MX=200005;
double ans=2e18;
int n,K,root,cur;
struct KD{
int l,r;
double v[2];
double L[2],U[2];
bool operator<(const KD &b) const{
return v[K]<b.v[K];
}
}t[MX];
void pushup(int p){
for(int i=0;i<2;i++){
t[p].L[i]=t[p].U[i]=t[p].v[i];
if(lc){
t[p].L[i]=min(t[p].L[i],t[lc].L[i]);
t[p].U[i]=max(t[p].U[i],t[lc].U[i]);
}
if(rc){
t[p].L[i]=min(t[p].L[i],t[rc].L[i]);
t[p].U[i]=max(t[p].U[i],t[rc].U[i]);
}
}
}
int build(int l,int r,int k){
if(l>r){
return 0;
}
int m=(l+r)>>1;
K=k;
nth_element(t+l,t+m,t+r+1);
t[m].l=build(l,m-1,k^1);
t[m].r=build(m+1,r,k^1);
pushup(m);
return m;
}
double sq(double x){
return x*x;
}
double dis(int p){
double s=0;
for(int i=0;i<2;i++){
s+=sq(t[cur].v[i]-t[p].v[i]);
}
return s;
}
double dis2(int p){
if(!p){
return 2e18;
}
double s=0;
for(int i=0;i<2;i++){
s+=sq(max(t[cur].v[i]-t[p].U[i],0.0))+sq(max(t[p].L[i]-t[cur].v[i],0.0));
}
return s;
}
void query(int p){
if(!p){
return;
}
if(p!=cur){
ans=min(ans,dis(p));
}
double dl=dis2(lc),dr=dis2(rc);
if(dl<dr){
if(dl<ans){
query(lc);
}
if(dr<ans){
query(rc);
}
}else{
if(dr<ans){
query(rc);
}
if(dl<ans){
query(lc);
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf",&t[i].v[0],&t[i].v[1]);
}
root=build(1,n,0);
for(cur=1;cur<=n;cur++){
query(root);
}
printf("%.4lf\n",sqrt(ans));
return 0;
}
这里空空如也
有帮助,赞一个