题目链接
计算最小点对的思想是：分治
注意：在下面代码中，如果使用宏定义来定义来替换取小函数min，则ＴＬＥ。
Accepted Code:
/*************************************************************************
> File Name: 1007.cpp
> Author: Stomach_ache
> Mail: [email protected]
> Created Time: 2014年06月10日 星期二 19时15分21秒
> Propose:
************************************************************************/ #include <cmath>
#include <string>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define INF (1000000000.0)
#define MAX_N (100010)
//#define X first
//#define Y second
//#define min(x, y) ((x) < (y) ? (x) : (y))
//typedef pair<double, double> pii;
struct pii {
double X, Y;
}; int n;
pii A[MAX_N], b[MAX_N]; double
min(double x, double y) {
return x < y ? x : y;
} bool
compare_x(pii a, pii b) {
return a.X < b.X;
} bool
compare_y(pii a, pii b) {
return a.Y < b.Y;
} double
get_dist(pii a, pii b) {
return sqrt((a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y));
} double
closest_pair(int low, int high) {
//if (high == low) return INF;
if (high - low == ) return get_dist(A[low], A[high]);
if (high - low == ) {
double d = get_dist(A[low], A[low+]);
d = min(d, get_dist(A[low], A[high]));
d = min(d, get_dist(A[low+], A[high]));
return d;
}
int m = (low + high) / ;
double x = A[m].X;
double d = min(closest_pair(low, m), closest_pair(m+, high)); // (1) int len = ;
for (int i = low; i <= high; i++) {
if (fabs(A[i].X - x) < d) {
b[len++] = A[i];
}
}
sort(b, b + len, compare_y);
for (int i = ; i < len; i++) {
for (int j = i+; j < len; j++) {
double dx = b[j].X - b[i].X;
double dy = b[j].Y - b[i].Y;
if (dy >= d) break;
d = min(d, sqrt(dx * dx + dy * dy));
}
} return d;
} void
solve() {
sort(A, A + n, compare_x);
printf("%.2f\n", closest_pair(, n - ) * 0.5);
} int
main(void) {
while (scanf("%d", &n) && n) {
for (int i = ; i < n; i++)
scanf("%lf %lf", &A[i].X, &A[i].Y); solve();
} return ;
}