BUZYKXZZY @ 2024-10-05 16:28:47
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int n;
const int maxn=100001;
struct point{
double x;
double y;
}arr1[maxn];
vector<point> arr2;
bool cmp1(point a,point b){
return a.x>b.x;
}
bool cmp2(point a,point b){
return a.y>b.y;
}
double dis(point a,point b){
double x=(a.x-b.x)*(a.x-b.x);
double y=(a.y-b.y)*(a.y-b.y);
double d=sqrt(x+y);
}
double solve(int left,int right){
if(left==right){
return 2e9;
}
if(left+1==right){
return dis(arr1[left],arr1[right]);
}
int mid=(left+right)/2;
double d1=solve(left,mid);
double d2=solve((mid+1),right);
double d=min(d1,d2);
//cout<<"d1="<<d1<<endl;
for(int i=0;i<n;i++){
if(fabs(arr1[i].x-arr1[mid].x)<d){
arr2.push_back(arr1[i]);
}
}
int index=arr2.size();
sort(arr2.begin(),arr2.end(),cmp2);
for(int i=0;i<index;i++){//计算中间最短距离
for(int j=i+1;j<index&&arr2[j].y-arr2[i].y<d;j++){
double d3=dis(arr2[i],arr2[j]);
if(d>d3){
d=d3;
}
}
}
return d;
}
int main() {
cin>>n;
for(int i=0;i<n;i++){
cin>>arr1[i].x>>arr1[i].y;
}
sort(arr1,arr1+n,cmp1);
double r=solve(0,n-1);
printf("%.4f",r);
return 0;
}
by KarmaticEnding @ 2024-10-05 16:30:10
@BUZYKXZZY
您的dis函数没有返回值吧