题意：有n个点，问其中某一对点的距离最小是多少
分析：分治法解决问题：先按照x坐标排序，求解(left, mid)和(mid+1, right)范围的最小值，然后类似区间合并，分离mid左右的点也求最小值
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> const int N = 1e5 + 5;
const double INF = 1e100;
struct Point {
double x, y;
bool flag;
bool operator < (const Point &rhs) const {
return x < rhs.x;
}
};
Point point[N*2];
int idy[N*2];
int n; bool cmp_y(int i, int j) {
return point[i].y < point[j].y;
} double squ(double x) {
return x * x;
} double get_dist(Point &a, Point &b) {
if (a.flag == b.flag) {
return INF;
}
return sqrt (squ (a.x - b.x) + squ (a.y - b.y));
} double min_dist(int left, int right) {
if (left == right) {
return INF;
}
else if (right - left == 1) {
return get_dist (point[left], point[right]);
} else {
int mid = left + right >> 1;
double ret = std::min (min_dist (left, mid), min_dist (mid + 1, right));
if (ret == 0) {
return ret;
}
int endy = 0;
for (int i=mid; i>=left&&point[mid].x-point[i].x<=ret; --i) {
idy[endy++] = i;
}
for (int i=mid+1; i<=right&&point[i].x-point[mid+1].x<=ret; ++i) {
idy[endy++] = i;
}
std::sort (idy, idy+endy, cmp_y);
for (int i=0; i<endy; ++i) {
for (int j=i+1; j<endy&&point[j].y-point[i].y<ret; ++j) {
ret = std::min (ret, get_dist (point[i], point[j]));
}
}
return ret;
}
} int main() {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
for (int i=0; i<2*n; ++i) {
scanf ("%lf%lf", &point[i].x, &point[i].y);
if (i < n) {
point[i].flag = false;
} else {
point[i].flag = true;
}
}
std::sort (point, point+2*n);
printf ("%.3f\n", min_dist (0, 2 * n - 1));
} return 0;
}
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> const int N = 1e5 + 5;
const double INF = 1e100;
struct Point {
double x, y;
};
Point point[N], py[N];
int n; bool cmp_x(const Point &a, const Point &b) {
return a.x < b.x;
}
bool cmp_y(const Point &a, const Point &b) {
return a.y < b.y;
} double squ(double x) {
return x * x;
} double get_dist(Point &a, Point &b) {
return sqrt (squ (a.x - b.x) + squ (a.y - b.y));
} double min_dist(int left, int right) {
if (left + 1 == right) {
return get_dist (point[left], point[right]);
} else if (left + 2 == right) {
return std::min (get_dist (point[left], point[left+1]),
std::min (get_dist (point[left], point[right]), get_dist (point[left+1], point[right])));
} else {
int mid = left + right >> 1;
double ret = std::min (min_dist (left, mid), min_dist (mid + 1, right));
int cnt = 0;
for (int i=mid; i>=left&&point[mid].x-point[i].x<=ret; --i) {
py[cnt++] = point[i];
}
for (int i=mid+1; i<=right&&point[i].x-point[mid+1].x<=ret; ++i) {
py[cnt++] = point[i];
}
std::sort (py, py+cnt, cmp_y);
for (int i=0; i<cnt; ++i) {
for (int j=i+1; j<cnt&&py[j].y-py[i].y<ret; ++j) {
ret = std::min (ret, get_dist (py[i], py[j]));
}
}
return ret;
}
} int main() {
while (scanf ("%d", &n) == 1) {
if (!n) {
break;
}
for (int i=0; i<n; ++i) {
scanf ("%lf%lf", &point[i].x, &point[i].y);
}
std::sort (point, point+n, cmp_x);
printf ("%.2f\n", min_dist (0, n - 1) / 2);
} return 0;
}