http://acm.hdu.edu.cn/showproblem.php?pid=1007
题意：平面上有n个点，问最近的两个点之间的距离的一半是多少。
思路：用分治做。把整体分为左右两个部分，那么有三种情况：最近的两个点都在左边，最近的两个点都在右边和最近的两个点一个在左边一个在右边。对于第一第二种情况，直接递归处理，分解成子问题就好了，主要是要处理第三种情况。最暴力的做法是O（n^2）的扫，这样肯定会TLE。那么要作一些优化。首先我们先递归处理得到第一种和第二种情况的答案的较小值，然后用这个答案去优化，即如果x上，某个点距离中点的距离在ans内的话，那么这个点是可能可以得到更优答案的，如果距离大于ans，那么肯定不能得到更优的答案。将这些点存起来，然后对y进行排序，暴力O（n^2）扫这些存起来的点，和第一个优化类似，如果当前两点之间y的距离大于等于ans，那么后面的答案肯定是大于ans的，直接break跳出去。
1 #include <cstring> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 using namespace std; 6 #define N 100010 7 #define INF 0x3f3f3f3f 8 struct node { 9 double x, y; 10 } p[N], tmp[N]; 11 12 double min(double a, double b) { return a < b ? a : b; } 13 14 bool cmpx(const node &a, const node &b) { return a.x < b.x; } 15 16 bool cmpy(const node &a, const node &b) { return a.y < b.y; } 17 18 double cal(node a, node b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } 19 20 double solve(int l, int r) { 21 if(r - l == 1) return cal(p[r], p[l]); 22 if(r - l == 2) return min(cal(p[l], p[r]), min(cal(p[r], p[r-1]), cal(p[r-1], p[l]))); 23 int mid = (l + r) >> 1, cnt = 0; 24 double ans = min(solve(l, mid), solve(mid + 1, r)); 25 for(int i = l; i <= r; i++) 26 if(p[i].x - ans <= p[mid].x && p[i].x + ans >= p[mid].x) 27 tmp[++cnt] = p[i]; 28 sort(tmp + 1, tmp + 1 + cnt, cmpy); 29 for(int i = 1; i <= cnt; i++) 30 for(int j = i + 1; j <= cnt; j++) 31 if(tmp[j].y - tmp[i].y >= ans) break; 32 else ans = min(ans, cal(tmp[i], tmp[j])); 33 return ans; 34 } 35 36 int main() { 37 int n; 38 while(scanf("%d", &n), n) { 39 for(int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y); 40 sort(p + 1, p + 1 + n, cmpx); 41 printf("%.2f\n", solve(1, n) / 2.0); 42 } 43 return 0; 44 }
HDU 1007：Quoit Design（分治求最近点对）
原文：http://www.cnblogs.com/fightfordream/p/6363345.html