Y_J_Y @ 2022-09-04 14:42:56
请求大佬帮助
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
struct Point {
double x,y;
}point[200005];
double dist(int a,int b) {
return sqrt((point[a].x-point[b].x)*(point[a].x-point[b].x)+(point[a].y-point[b].y)*(point[a].y-point[b].y));
}
double solve(int l,int r) {
if(l==r) return inf;
if(l==r-1) return dist(l,r);
int mid=(l+r)>>1;
double min_d=min(solve(l,mid),solve(mid+1,r));
for(int i=l;i<=mid;i++) {
if(!(abs(point[mid].x-point[i].x)<min_d&&abs(point[mid].y-point[i].y)<min_d)) continue;
for(int j=mid+1;j<=r;j++) {
if(!(abs(point[mid].x-point[j].x)<min_d&&abs(point[mid].y-point[j].y)<min_d)) continue;
min_d=min(min_d,dist(i,j));
}
}
return min_d;
}
bool cmp(Point a,Point b) {
return a.x<b.x;
}
int main() {
int n;n=read();
for(int i=1;i<=n;i++) {
scanf("%lf%lf",&point[i].x,&point[i].y);
}
sort(point+1,point+n+1,cmp);
double ans =solve(1,n);
printf("%.4lf",ans);
return 0;
}
by Y_J_Y @ 2022-09-04 15:04:52
已过,原因是因为后面的y并没有排序,所以不能用mid的y来做标准