Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 30505 Accepted Submission(s): 8017
2 0 0 1 1 2 1 1 1 1 3 -1.5 0 0 0 0 1.5 0
0.71 0.00 0.75
题意:给定n个点,求距离最短的两点的距离的一半。
题解:开始用暴力法,结果超时,然后换成分治就过了,分治的过程是先将每个点的坐标读入到数组里,再将数组按照x坐标排序,然后分治找最小值,递归终止条件是只剩两个元素或三个元素,但是若仅按照x排序最终结果不一定是最小值,因为有可能左边的元素与右边的元素构成最小值,所以需要再根据y值进行一次排序,此时数据规模已经相当小了,可以用暴力直接求解。
分治代码:
#include <stdio.h> #include <math.h> #include <algorithm> #define maxn 100002 using std::sort; struct Node{ double x, y; } arr[maxn], temp[maxn]; bool cmpx(Node a, Node b) { return a.x < b.x; } bool cmpy(Node a, Node b) { return a.y < b.y; } double calDist(int i, int j) { double x = arr[i].x - arr[j].x; double y = arr[i].y - arr[j].y; return sqrt(x * x + y * y); } double divideAndConquer(int l, int r) { if(r - l == 1) return calDist(l, r); else if(r - l == 2){ double a = calDist(l, l + 1); double b = calDist(l + 1, r); double c = calDist(l, r); if(b > c) b = c; return a < b ? a : b; } int mid = (l + r) >> 1, i, j, id = 0; double a = divideAndConquer(l, mid); double b = divideAndConquer(mid + 1, r); double min = a < b ? a : b; for(i = l; i <= r; ++i) if(fabs(arr[i].x - arr[mid].x) < min) temp[id++] = arr[i]; sort(temp, temp + id, cmpy); for(i = 0; i < id; ++i) for(j = i + 1; j < id; ++j){ a = temp[j].y - temp[i].y; if(a >= min) break; b = temp[j].x - temp[i].x; a = sqrt(a * a + b * b); if(a < min) min = a; } return min; } int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int n, i, j; double ans, x, y, len; while(scanf("%d", &n), n){ for(i = 0; i < n; ++i) scanf("%lf%lf", &arr[i].x, &arr[i].y); sort(arr, arr + n, cmpx); printf("%.2lf\n", divideAndConquer(0, n - 1) / 2); } return 0; }
原TLE代码:
#include <stdio.h> #include <math.h> #define maxn 100002 struct Node{ double x, y; } arr[maxn]; double cal(int i, int j) { double x = arr[i].x - arr[j].x; double y = arr[i].y - arr[j].y; return sqrt(x * x + y * y); } int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int n, i, j; double ans, x, y, len; while(scanf("%d", &n), n){ for(i = 0, ans = -1; i < n; ++i){ scanf("%lf%lf", &arr[i].x, &arr[i].y); for(j = 0; j < i; ++j){ len = cal(i, j); if(len < ans || ans < 0) ans = len; } } printf("%.2lf\n", ans / 2); } return 0; }
HDU1007 Quoit Design 【分治】,布布扣,bubuko.com
原文:http://blog.csdn.net/chang_mu/article/details/38274931