为什么最后一个测试点过不了啊
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Point {
double x, y;
int id;
};
int ret_1 = 0, ret_2 = 0;
double ans = (double)__INT64_MAX__;
Point p[200001];
int tmp[2000];
double distance(const Point& a, const Point& b) {
return pow(pow(a.x - b.x, 2) + pow(a.y - b.y, 2), 0.5);
}
void Update(int id_1, int id_2, double dis) {
if (id_1 > id_2) swap(id_1, id_2);
if (dis == ans) {
if (ret_1 > id_1 || ret_1 == id_1 && ret_2 > id_2) {
ret_1 = id_1, ret_2 = id_2;
}
}
else {
ret_1 = id_1, ret_2 = id_2, ans = dis;
}
}
int cmpPoint(Point& a, Point& b) {
return a.x < b.x;
}
int cmpArr(int x, int y) {
return p[x].x < p[y].x;
}
void findClosest(int left, int right) {
if (left == right) {
return;
}
if (left + 1 == right) {
auto cur = distance(p[left], p[right]);
if (ans > cur) {
Update(p[left].id, p[right].id, cur);
return;
}
}
int mid = (left + right) >> 1;
findClosest(left, mid);
findClosest(mid + 1, right);
int k = 0;
for (int i = left; i <= right; ++i) {
if (fabs(p[mid].x - p[i].x) <= ans) {
tmp[k++] = i;
}
}
sort(tmp, tmp + k, cmpArr);
for (int i = 0; i < k; ++i) {
for (int j = i + 1; j < k && p[tmp[j]].y - p[tmp[i]].y <= ans; ++j) {
if (ans > distance(p[tmp[i]], p[tmp[j]])) {
Update(p[tmp[i]].id, p[tmp[j]].id, distance(p[tmp[i]], p[tmp[j]]));
}
}
}
}
signed main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> p[i].x >> p[i].y;
p[i].id = i;
}
sort(p, p + n, cmpPoint);
findClosest(0, n - 1);
printf("%.4lf\n", ans);
return 0;
}