最近点对的裸题
利用分治去搞搞即可
代码：
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int N = 100005;struct Point {double x, y;void read() {scanf("%lf%lf", &x, &y);}};bool cmpx(Point a, Point b) {return a.x < b.x;}bool cmpy(Point a, Point b) {return a.y < b.y;}double dis(Point a, Point b) {double dx = a.x – b.x;double dy = a.y – b.y;return sqrt(dx * dx + dy * dy);}int n;Point p[N], tmp[N];int tn;double gao(double ans) {sort(tmp, tmp + tn, cmpy);for (int i = 0; i < tn; i++) {for(int j = i + 1; j < tn && tmp[j].y – tmp[i].y < ans; j++) {ans = min(ans, dis(tmp[i], tmp[j]));}}return ans;}double ClosePoint(int l, int r) {if (r – l + 1 <= 3) {tn = 0;for (int i = l; i <= r; i++)tmp[tn++] = p[i];return gao(1e20);}int mid = (l + r)>>1;double s = min(ClosePoint(l, mid), ClosePoint(mid + 1, r));tn = 0;for (int i = l; i <= r; i++) {if (fabs(p[i].x – p[mid].x) < s)tmp[tn++] = p[i];}return gao(s);}int main() {while (~scanf("%d", &n) && n) {for (int i = 0; i < n; i++)p[i].read();sort(p, p + n, cmpx);printf("%.2f\n", ClosePoint(0, n – 1) / 2);}return 0;}
，怎么能研究出炸药呢?爱迪生不经历上千次的来自失败，怎么能发明电灯呢?
