题目描述
在一个长方形框子里，最多有N（0≤N≤6）个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这N个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不同的油滴不会相互融合）
注：圆的面积公式V=pi*r*r，其中r为圆的半径。
输入输出格式
输入格式：
第1行一个整数N。
第2行为长方形边框一个顶点及其对角顶点的坐标，x,y,x’,y’。
接下去N行，每行两个整数xi,yi，表示盒子的N个点的坐标。
以上所有的数据都在[-1000，1000]内。
输出格式：
一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）
输入输出样例
输入样例#1：
2 20 0 10 10 13 3 17 7
输出样例#1：
50
对于样例的理解，第一个油滴扩散半径为3，因为受矩形框的限制。第二个油滴扩散半径小于3，因为受第一个油滴的限制。r2受r1限制，即r2<=dis-r1. （dis为圆心距）
枚举n个点的先后顺序。对于第i个油滴，能扩散到的半径Ri只受矩形和前i-1个油滴半径的约束，为方便求Ri，可以先预处理出各个点之间的距离dis[i][j]。
//Gang
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define FOR(x,y,z) for(int x=y;x<=z;x++)
#define REP(x,y,z) for(int x=y;x>=z;x--)
#define ll long long
using namespace std;
int n;
][],x,y,x2,y2,a[][];
],r;//r为准备放置的油滴的扩散半径
double maxn;
];
);
void dfs(int steps,double s)//steps位当前步数，s为当前面积
{
)
{
if(s>maxn)
maxn=s;
}
else
FOR(k,,n)
if(!vis[k])
{
//矩形和已放置的油滴约束了r的大小
r=fabs(y2-a[k][]);
]))r=fabs(y-a[k][]);
]))r=fabs(x2-a[k][]);
]))r=fabs(x-a[k][]);
FOR(i,,n)
{
if(vis[i])
{
if(r>dis[k][i]-R[i])r=dis[k][i]-R[i];
}
}
//注意r不能为负
r=r<?:r;
R[k]=r;
vis[k]=;
dfs(steps+,s+pi*r*r);
vis[k]=;
R[k]=0.0;
}
}
int main()
{
scanf("%d%lf%lf%lf%lf",&n,&x,&y,&x2,&y2);
FOR(i,,n)scanf(],&a[i][]);
FOR(i,,n)
{
FOR(j,,i)
{
//预处理出油滴间距dis
dis[i][j]=sqrt(pow(fabs(a[i][]-a[j][]),)+pow(fabs(a[i][]-a[j][]),));
dis[j][i]=dis[i][j];
}
}
double S=fabs(x-x2)*fabs(y-y2);//矩形面积
dfs(,0.0);
printf("%.0lf",floor(S-maxn+0.5));
;
}