给定二维平面内若干点的的坐标,问最近点对的距离。
暴力pass,必须是分治。可以把平面上的点分为左右两部分,最近的点对一定是左边的最近点对,右边的最近点对和左右分界线上的最近点对中距离最短的那一对。
题目对程序的速度性要求很高,跑t了好多发。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <algorithm> #define SIZE 100000 using namespace std; struct Node { double x, y; }p[SIZE]; int n; int index[SIZE]; bool cmpx(const Node a, const Node b) { return a.x < b.x; } bool cmpy(const int a, const int b) { return p[a].y < p[b].y; } double dis(const Node& a, const Node& b) { double tmp = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); return tmp; } double m(double a, double b) { return a < b ? a : b; } double mindis(int left, int right) { if (left + 1 == right) return dis(p[left], p[right]); else if (left + 2 == right) return m(dis(p[left], p[left+1]), m(dis(p[left+1], p[right]), dis(p[left], p[right]))); else { int mid = (left + right) >> 1; double tmpdis = m(mindis(left, mid), mindis(mid+1, right)); double a = p[mid].x - tmpdis; double b = p[mid].x + tmpdis; int len = 0; for (int i = left; i <= right; i++) { if (p[i].x > a && p[i].x < b) index[len++] = i; } sort(index, index+len, cmpy); for(int i = 0; i < len; i++) { for(int j = i+1; j < len; j++) { if (p[index[j]].y - p[index[i]].y > tmpdis) break; tmpdis = m(tmpdis, dis(p[index[i]], p[index[j]])); } } return tmpdis; } } int main() { #ifdef BellWind freopen("1007.in", "r", stdin); #endif // BellWind // int cnt = 0; while (~scanf("%d", &n) && n) { for (int i = 0; i < n; i++) { scanf("%lf%lf", &p[i].x, &p[i].y); } sort(p, p+n, cmpx); double dis = mindis(0, n-1); printf("%.2lf\n", sqrt(dis)/2.0); } return 0; }