题目链接：https://vjudge.net/problem/FZU-1515 题意：给你一个立方体，立方体里有n个点，每个点代表一个圆心，你可以选择一个点开始扩充气球，知道碰到壁，或者碰到其他气球为止，问你立方体剩下的体积的最小值（四舍五入） 解析：挺水的一道题的，直接枚举就好，如果一个气球无法扩充可以跳过他，我也是莫名其妙wa了一版，还是自己太水了
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> #include <vector> #include <queue> #include <set> using namespace std; const int maxn = 10; const double inf = 0x7ffffff; const double pi = acos(-1.0); struct point { double x,y,z; double r; }a[maxn],s,e; int n; double ans; double dis(point p1,point p2) { double tmp1 = (p1.x-p2.x)*(p1.x-p2.x); double tmp2 = (p1.y-p2.y)*(p1.y-p2.y); double tmp3 = (p1.z-p2.z)*(p1.z-p2.z); return sqrt(tmp1+tmp2+tmp3); } double slove(int i) { double t1 = min(fabs(a[i].x-e.x),fabs(a[i].x-s.x)); double t2 = min(fabs(a[i].y-e.y),fabs(a[i].y-s.y)); double t3 = min(fabs(a[i].z-e.z),fabs(a[i].z-s.z)); double r = min(t1,t2); r = min(t3,r); return r; } double area(double r) { return 4.0*r*r*r*pi/3.0; } int main() { while(~scanf("%d",&n)) { scanf("%lf %lf %lf",&s.x,&s.y,&s.z); scanf("%lf %lf %lf",&e.x,&e.y,&e.z); double total = fabs((s.x-e.x)*(s.y-e.y)*(s.z-e.z)); memset(a,0,sizeof(a)); for(int i=0;i<n;i++) scanf("%lf %lf %lf",&a[i].x,&a[i].y,&a[i].z); double ans = 0; int vis[maxn]; for(int i=0;i<n;i++) vis[i] = i; do { for(int i=0;i<n;i++) a[i].r = 0; double tmp = 0; for(int i=0;i<n;i++) { a[vis[i]].r =slove(vis[i]); for(int j=0;j<n;j++) { if(i==j || a[vis[j]].r==0) continue; double tt = dis(a[vis[j]],a[vis[i]])-a[vis[j]].r; tt = max(tt,0.0); a[vis[i]].r = min(a[vis[i]].r,tt); } tmp += area(a[vis[i]].r); } ans = max(tmp,ans); }while(next_permutation(vis,vis+n)); printf("%.0f\n",fabs(total-ans)); } return 0; } /* 2 0 0 0 10 10 10 3 3 3 7 7 7 4 73 256 -38 -175 944 136 -37 332 1 -63 743 64 48 472 -32 35 753 38 6 808 877 -957 661 329 -738 763 572 -792 687 539 -879 673 795 -811 679 500 -783 717 545 -883 667 629 -825 774 27763968 16491870 */