WA求调
查看原帖
WA求调
1227383
MPLN楼主2025/1/22 20:57
#include<bits/stdc++.h>
using namespace std;
int n;
double ans=DBL_MAX;
struct node{int x,y;}a[200010],b[200010];
bool cmp1(node p,node q){return p.x<q.x;}
bool cmp2(node p,node q){return p.y<q.y;}
double dis(int p,int q){return sqrt((double)((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,dis(l,r));
    return;
  }
  int mid=(l+r)/2;
  f(l,mid),f(mid+1,r);
  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].y-b[i].y<=ans&&q<=bcnt) q++;
    for(int j=i+1;j<q;j++)
      ans=min(ans,dis(i,j));
  }
}
int 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("%.4lf",ans);
  return 0;
}
2025/1/22 20:57
加载中...