黑書計劃 - ICPC2002 WF Balloons in a Box

ACM-ICPC Live Archive

題目大意：一個盒子里有n(n≤6)個點，在每個點上放一個氣球，氣球會開始膨脹，問按照什麼順序放最後氣球的體積最大。

思路：黑書的第一題。就是普通的枚舉，6的排列最多只有720種，一個一個試就好了。每次檢查一下是否膨脹到邊緣或者是和其他氣球接觸，找到最大的半徑，然後放一個氣球。聽上去很簡單，然而我好像在不知所以的地方寫渣被卡精度WA了30餘發……後來重構代碼，AC了……

#include <bits/stdc++.h> nusing namespace std; nconst double pi = acos(-1.0); nndouble x[15], y[15], z[15], r[15]; ndouble X1, Y1, Z1, X2, Y2, Z2, maxV; nint n, ty[15]; nbool vis[15]; nninline double getR(int i) n{n return min(min(fabs(x[i] - X1), fabs(x[i] - X2)), min(min(fabs(y[i] - Y1), fabs(y[i] - Y2)), min(fabs(z[i] - Z1), fabs(z[i] - Z2)))); n} nninline double dist(int a, int b) n{ n return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]) + (z[a] - z[b]) * (z[a] - z[b])); n} nninline void getV() n{ n double a, v = 0; n for (register int i = 0;i < n; ++i) { n a = getR(ty[i]); n for (register int j = 0; j < i; ++j) n a = min(a, dist(ty[i], ty[j]) - r[ty[j]]); n r[ty[i]] = (a < 0) ? 0 : a; n if (a <= 0) continue; n v += (4.0 / 3 * pi * r[ty[i]] * r[ty[i]] * r[ty[i]]); n } n maxV = max(maxV, v); n} nninline void dfs(int cur) n{ n if (cur == n) getV(); n elsen for (register int i = 0; i < n; ++i) n if (!vis[i]) { n ty[cur] = i; n vis[i] = 1; n dfs(cur + 1); n vis[i] = 0; n } n} nnint main() n{ n int kase = 0; n while(scanf("%d", &n) == 1 && n) n { n scanf("%lf%lf%lf", &X1, &Y1, &Z1); n scanf("%lf%lf%lf", &X2, &Y2, &Z2); n for (register int i = 0; i < n; ++i) n scanf("%lf%lf%lf", &x[i], &y[i], &z[i]); n maxV = 0; n memset(vis, 0, sizeof(vis)); n dfs(0); n printf("Box %d: %.0lfnn", ++kase, ((fabs((X1 - X2) * (Y1 - Y2) * (Z1 - Z2))) - maxV)); nn } n return 0; n} n

推薦閱讀：