[洛谷P1378]油滴扩展
题目大意：有n滴油在一个平面上，油滴按顺序依次扩展（呈圆形），当碰到其他油滴或平面边界时停止扩展，让你设计一个扩展顺序，使平面剩余面积尽可能小。
解题思路：由于$nleq 6$，我们可以dfs油滴扩展顺序，然后计算每个油滴能扩展的半径即可。时间复杂度$O(n!)$。
注意：①$pi$的精度不能太小；②有些油滴包含在另一个油滴内部，则不能扩展；③题目要求四舍五入，则保留0位小数即可。
当然也可以用STL的全排列算法把所有排列求出来，然后按照排列顺序扩展。
C++ Code：
#include<cstdio>
#include<cstring>
#include<cmath>
const double pi=3.14159265358979323846264338;
double ans=1000000000000000.0;
struct oil{
int x,y;
}a[8];
bool b[8];
double r[8];
int d[8],x_1,x_2,y_1,y_2,n;
inline double min(double a,double b){return(a<b)?a:b;}
void dfs(int t){
if(t>n){
double p=fabs((x_2-x_1)*(y_2-y_1));
for(int i=1;i<=n;++i)p-=pi*r[d[i]]*r[d[i]];
if(ans>p)ans=p;
return;
}
for(int i=1;i<=n;++i)
if(!b[i]){
b[i]=true;
d[t]=i;
double R=min(min(fabs(a[i].x-x_1),fabs(a[i].x-x_2)),min(fabs(a[i].y-y_1),fabs(a[i].y-y_2)));
for(int j=1;j<t;++j)
R=min(R,sqrt((a[d[j]].x-a[i].x)*(a[d[j]].x-a[i].x)+(a[d[j]].y-a[i].y)*(a[d[j]].y-a[i].y))-r[d[j]]);
if(R<0.0)R=0.0;
r[i]=R;
dfs(t+1);
b[i]=false;
}
}
int main(){
scanf("%d%d%d%d%d",&n,&x_1,&y_1,&x_2,&y_2);
for(int i=1;i<=n;++i)scanf("%d%d",&a[i].x,&a[i].y);
memset(b,0,sizeof b);
dfs(1);
printf("%.0f
",ans);
return 0;
}