关键字：搜索，模拟。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
在一个长方形框子里，最多有N（0≤N≤6）个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这N个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不同的油 滴不会相互融合）
注：圆的面积公式V=pi*r*r，其中r为圆的半径。
Input Format
第1行一个整数N。
第2行为长方形边框一个顶点及其对角顶点的坐标，x,y,x',y’。
接下去N行，每行两个整数xi,yi，表示盒子的N个点的坐标。
以上所有的数据都在[-1000，1000]内。
Output Format
一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）。
Sample Input #1
2
20 0 10 10
13 3
17 7
Sample Output #1
50
简单的搜索题，枚举每滴油滴落的顺序，油滴的半径就是与边框相切，或者与其它油滴外切的最小半径。
惟一需要注意的细节是：如果新的油滴中心位于已有的油滴之内，那么新油滴半径为0.
#include <stdio.h>
#include <math.h>
int n,xa,ya,xb,yb,x[10],y[10];
short vis[10];
double ans = 0,r[10];
int abs(int num)
{
return num>0?num:-num;
}
double max(double a, double b)
{
return a>b?a:b;
}
double min(double a, double b)
{
return a<b?a:b;
}
void dfs(int dep,double tans)
{
int i,j;
if(dep>n) {ans = ans>tans?ans:tans; return;}
for(i=1;i<=n;i++)
{
if(vis[i]) continue;
vis[i] = 1;
r[i] = min(abs(y[i]-ya),abs(y[i]-yb));
r[i] = min(r[i],min(abs(x[i]-xa),abs(x[i]-xb)));
for(j=1;j<=n;j++)
{
if(i == j || !vis[j]) continue;
r[i] = max(0,min(r[i],sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-r[j]));
}
dfs(dep+1,tans+3.1415926535*r[i]*r[i]);
vis[i] = 0;
}
}
int main()
{
int i;
scanf("%d%d%d%d%d",&n,&xa,&ya,&xb,&yb);
for(i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
dfs(1,0);
printf("%d",(int)(abs(xa-xb)*abs(ya-yb)-ans+0.5));
return 0;
}
评论 (0)
