WA求调
查看原帖
WA求调
1227383
MPLN楼主2025/1/22 20:46
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
double ans=DBL_MAX;
struct node{int x,y;}a[50010];
bool cmp1(node p,node q){return p.x<q.x;}
bool cmp2(node p,node q){return p.y<q.y;}
int dis(int p,int q){return (a[p].x-a[q].x)*(a[p].x-a[q].x)+(a[p].y-a[q].y)*(a[p].y-a[q].y);}
void f(int l,int r){
  if(l>=r) return;
  if(r-l==1){
    ans=min(ans,sqrt((double)dis(l,r)));
    return;
  }
  int mid=(l+r)/2;
  f(l,mid),f(mid+1,r);
  node b[50010];
  int bcnt=0;
  for(int i=l;i<=r;i++)
    if(abs(a[i].x-a[mid].x)<ans)
      b[++bcnt]=a[i];
  sort(b+1,b+bcnt+1,cmp2);
  for(int i=1,q=1;i<=bcnt;i++){
    while(b[q+1].y-b[i].y<=ans&&q+1<=bcnt) q++;
    for(int j=i+1;j<=q;j++)
      ans=min(ans,sqrt((double)dis(i,j)));
  }
}
signed main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i].x>>a[i].y;
  }
  sort(a+1,a+n+1,cmp1);
  f(1,n);
  printf("%.2lf",ans);
  return 0;
}
2025/1/22 20:46
加载中...