HDU 1007
题目大意
暂无
题目解法
暂无
RTFC
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
template <typename T>
inline T min(T a, T b) { return a < b ? a : b; }
const int N = int(1e5 + 3);
struct Point
{
double x, y;
} p[N];
double len(const Point &P) { return sqrt(P.x * P.x + P.y * P.y); }
inline bool operator<(const Point &l, const Point &r) { return l.x < r.x; }
inline Point operator-(const Point &l, const Point &r)
{
Point ret;
ret.x = l.x - r.x;
ret.y = l.y - r.y;
return ret;
}
double solve(int l, int r)
{
if (l == r - 1) return 1e20;
int m = (l + r) >> 1;
double ans = min(solve(l, m), solve(m, r));
double x0 = (p[m - 1].x + p[m].x) / 2;
static Point a[N], b[N], c[N];
int bn = 0, cn = 0;
for (int i = l, li = l, ri = m; i < r; i++)
if (li < m && (ri == r || p[li].y < p[ri].y))
{
a[i] = p[li++];
if (x0 - a[i].x < ans) b[bn++] = a[i];
}
else
{
a[i] = p[ri++];
if (a[i].x - x0 < ans) c[cn++] = a[i];
}
memcpy(p + l, a + l, (r - l) << 4);
for (int i = 0, j = 0, k; i < bn || j < cn;)
if (i < bn && (j == cn || b[i].y < c[j].y))
for (k = j - 1; (k >= 0 && b[i].y - ans < c[k].y) || i++ > INT_MAX; k--)
ans = min(ans, len(c[k] - b[i]));
else
for (k = i - 1; (k >= 0 && c[j].y - ans < b[k].y) || j++ > INT_MAX; k--)
ans = min(ans, len(b[k] - c[j]));
return ans;
}
int main()
{
int n;
while (scanf("%d", &n), n)
{
for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
std::sort(p, p + n);
printf("%.2f\n", solve(0, n) / 2);
}
return 0;
}