比赛 20120925 评测结果 WWWAAWWWAA
题目名称 油滴扩展 最终得分 40
用户昵称 Truth.Cirno 运行时间 0.004 s
代码语言 C++ 内存使用 2.11 MiB
提交时间 2012-09-25 21:54:28
显示代码纯文本
#include <cstdio>
#include <cmath>
//#include <memory.h>
using namespace std;

const double PI=3.1415926;

int n,rec[10];
double a1,b1,a2,b2,ao[10],bo[10],r[10],maxsqu;
bool used[10];

double mtzdou(double a)
{
	if (a<0)
		return(0);
	return(a);
}

double absdou(double a)
{
	if(a<0)
		return(-a);
	return(a);
}

double mindou(double a,double b)
{
	if (a>b)
		return(b);
	return(a);
}

double maxdou(double a,double b)
{
	if (a<b)
		return(b);
	return(a);
}

void work(void)
{
	int i,j,pi,pj;
	double rt,squ=0;
//	memset(r,0,sizeof(r));
	for (i=1;i<=n;i++)
	{
		pi=rec[i];
		rt=mindou(mtzdou(ao[pi]-a1),mtzdou(bo[pi]-b1));
		rt=mindou(rt,mtzdou(a2-ao[pi]));
		rt=mindou(rt,mtzdou(b2-bo[pi]));
		for (j=1;/*j<=n*/j<i;j++)
		{
//			if (j==i)
//				continue;
			pj=rec[j];
			rt=mindou(rt,absdou(mtzdou(sqrt((ao[pj]-ao[pi])*(ao[pj]-ao[pi])+(bo[pj]-bo[pi])*(bo[pj]-bo[pi]))-r[pj])));
		}
		r[pi]=rt;
		squ+=rt*rt*PI;
	}
	maxsqu=maxdou(maxsqu,squ);
}

void dfs(int deep)
{
	if (deep>n)
	{
		work();
		return;
	}
	int i;
	for (i=1;i<=n;i++)
		if (!used[i])
		{
			used[i]=true;
			rec[deep]=i;
			dfs(deep+1);
//			rec[deep]=0;
			used[i]=false;
		}
}

int main(void)
{
	freopen("oilbox.in","r",stdin);
	freopen("oilbox.out","w",stdout);
	int i;
	scanf("%d",&n);
	scanf("%lf%lf%lf%lf",&a1,&b1,&a2,&b2);
	for (i=1;i<=n;i++)
		scanf("%lf%lf",&ao[i],&bo[i]);
	dfs(1);
	printf("%.0lf\n",(a2-a1)*(b2-b1)-maxsqu);
	return(0);
}