原創(chuàng)
首先記下一這個(gè)知識(shí)點(diǎn)：C語言程序中浮點(diǎn)數(shù)類型（%.2lf）編譯器默認(rèn)四舍五入展哭，（最好自行測試一遍色乾，可能不同平臺(tái)使用的C語言版本不同姑食，語言標(biāo)準(zhǔn)也有細(xì)微的區(qū)別。）如果不需要四舍五入芭梯，則要自行處理（浮點(diǎn)數(shù)险耀，x=需要保留的小數(shù)位+1）。（已經(jīng)寫過測試代碼進(jìn)行了驗(yàn)證＞链Ｋξ！）累奈。另外贬派，float精度是
，能保證6位澎媒，double的精度是
搞乏，能保證15位。
問題描述
你要寫一個(gè)程序戒努，使得能夠模擬在長方體的盒子里放置球形的氣球请敦。
接下來是模擬的方案。假設(shè)你已知一個(gè)長方體的盒子和一個(gè)點(diǎn)集柏卤。每一個(gè)點(diǎn)代表一個(gè)可以放置氣球的位置冬三。在一個(gè)點(diǎn)上放置一個(gè)氣球，就是以這個(gè)點(diǎn)為球心缘缚，然后讓這個(gè)球膨脹，直到觸及盒子的邊緣或者一個(gè)之前已經(jīng)被放置好的氣球敌蚜。你不能使用一個(gè)在盒子外面或者在一個(gè)之前已經(jīng)放置好的氣球里面的點(diǎn)桥滨。但是，你可以按你喜歡的任意順序使用這些點(diǎn)弛车，而且你不需要每個(gè)點(diǎn)都用齐媒。你的目標(biāo)是按照某種順序在盒子里放置氣球，使得氣球占據(jù)的總體積最大纷跛。
你要做的是計(jì)算盒子里沒被氣球占據(jù)的體積喻括。
輸入格式
第一行包含一個(gè)整數(shù)n表示集合里點(diǎn)的個(gè)數(shù)（1≤n≤6）。第二行包含三個(gè)整數(shù)表示盒子的一個(gè)角落的(x,y,z)坐標(biāo)贫奠，第三行包含與之相對(duì)的那個(gè)角落的(x,y,z)坐標(biāo)唬血。接下來n行望蜡，每行包含三個(gè)整數(shù)，表示集合中每個(gè)點(diǎn)的(x,y,z)坐標(biāo)拷恨。這個(gè)盒子的每維的長度都是非零的脖律，而且它的邊與坐標(biāo)軸平行。
輸出格式
只有一行腕侄，為那個(gè)盒子沒被氣球占據(jù)的最小體積（四舍五入到整數(shù)）小泉。
樣例輸入
2
0 0 0
10 10 10
3 3 3
7 7 7
樣例輸出
774
數(shù)據(jù)規(guī)模和約定
所有坐標(biāo)的絕對(duì)值小于等于1000
對(duì)于20%的數(shù)據(jù)：n=1
對(duì)于50%的數(shù)據(jù)：1≤n≤3
對(duì)于100%的數(shù)據(jù)：1≤n≤6
分析：題意核心為限制箱子內(nèi)點(diǎn)可作為氣球中心，且氣球膨脹只能相切于箱子或者其他氣球的條件冕杠，得到空間利用最大化微姊。
相切只需要滿足最強(qiáng)條件即可，即最先到達(dá)的距離分预，分兩種可能兢交，一種是相切于箱子的6個(gè)面中的某一面，一種是相切于其他氣球（由球心和半徑確定）噪舀。
1.相切于6個(gè)面中的某一面只是基于比較球心到這六個(gè)面距離的比較魁淳。
2.相切于其他氣球采用先入為主的策略（并且后面使用全排列，保證每一種情況都經(jīng)過比較）与倡，只和已經(jīng)確定下來的氣球作比較界逛。相切的情況一定能通過達(dá)到最小的兩點(diǎn)間距離減去零一球半徑得到。
你的目標(biāo)是按照某種順序在盒子里放置氣球纺座，使得氣球占據(jù)的總體積最大息拜。即枚舉
每一種可能，記錄最大值即可净响。
其中枚舉可使用next_permutation（）函數(shù)少欺，其中變量為數(shù)組起始位置和結(jié)束位置（+1？）馋贤，其包含在頭文件<algorithm>中赞别。
代碼如下，簡單枚舉每種排列計(jì)算最優(yōu)即可
//回宿舍改
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
const double pi=acos(-1.0);
using namespace std;
typedef struct vp
{
double x,y,z;
double r;
}P;
P e,s,vv[20];
double l,w,h;
int n;
bool judge(double x,double y,double z)
{
if(fabs(x-e.x)>l||fabs(x-s.x)>l)
return true;
if(fabs(y-e.y)>w||fabs(y-s.y)>w)
return true;
// if(fabs(x-e.z)>h||fabs(x-s.z)>h)
// bug如上所示
if(fabs(z-e.z)>h||fabs(z-s.z)>h)
return true;
return false;
}
double mindis(double x,double y,double z)
{
double t1=min(fabs(x-e.x),fabs(x-s.x));
double t2=min(fabs(y-e.y),fabs(y-s.y));
double t3=min(fabs(z-e.z),fabs(z-s.z));
double p=min(t1,t2);
double pp=min(t3,p);
return pp;
}
double point_dis(P p1,P p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
}
double area(double r)
{
return r*r*r*pi*4/3.0;
}
int main()
{
int a[10];
while(cin>>n&&n>0)
{
cin>>e.x>>e.y>>e.z;
cin>>s.x>>s.y>>s.z;
l=fabs(e.x-s.x);
h=fabs(e.z-s.z);
w=fabs(e.y-s.y);
double total=l*h*w;
//cout<<total<<endl;
for(int i=0;i<n;i++)
{
cin>>vv[i].x>>vv[i].y>>vv[i].z;
a[i]=i;
}
double maxx=0;
do
{
double ini=0;
for(int i=0;i<n;i++)
{
if(judge(vv[a[i]].x,vv[a[i]].y,vv[a[i]].z))
continue;
vv[a[i]].r=mindis(vv[a[i]].x,vv[a[i]].y,vv[a[i]].z);
for(int j=0;j<i;j++)
{
// if(judge(vv[a[i]].x,vv[a[i]].y,vv[a[i]].z))
// continue;
double diss=point_dis(vv[a[i]],vv[a[j]])-vv[a[j]].r;
if(diss<0)diss=0;
vv[a[i]].r=min(vv[a[i]].r,diss);
}
ini+=area(vv[a[i]].r);
// cout<<ini<<endl;
}
maxx=max(maxx,ini);
// cout<<total<<endl<<ini<<endl;
// cout<<vv[1].x<<"haha"<<vv[0].y<<endl;
}while(next_permutation(a,a+n));
//cout<<maxx<<endl;
printf("%.0lf\n",total-maxx);
}
return 0;
}
