比赛 20120925 评测结果 AAAAAAAAAA
题目名称 油滴扩展 最终得分 100
用户昵称 苏轼 运行时间 0.006 s
代码语言 C++ 内存使用 2.50 MiB
提交时间 2012-09-25 20:20:40
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
const double pi=3.1415926;
int n;
double xx1,xx2,yy1,yy2;
double w[7][2]={0},q[7]={0};
bool used[7]={0};
double answer=0,temp=0;
void dfs(int x);
int main()
{
	freopen ("oilbox.in","r",stdin);
	freopen ("oilbox.out","w",stdout);
	cin>>n>>xx1>>yy1>>xx2>>yy2;
	if (xx1>xx2)
	{
		double tmp;
		tmp=xx1;
		xx1=xx2;
		xx2=tmp;
	}
	if (yy1>yy2)
	{
		double tmp;
		tmp=yy1;
		yy1=yy2;
		yy2=tmp;
	}
	for (int i=0;i<n;i++)
	{
		cin>>w[i][0]>>w[i][1];
	}
	dfs(0);
	int ans=0;
	if (((int)(answer*10)%10)<5)
	{
		ans=answer*10;
		ans/=10;
	}
	else
	{
		ans=answer*10+10;
		ans/=10;
	}
	cout<<((int)((int)(yy2-yy1)*(xx2-xx1))-ans);
	return 0;
}
void dfs(int x)
{
	if (x==n)
	{
		if (temp>answer)
			answer=temp;
	}
	else
	{
		for (int i=0;i<n;i++)
		{
			if (used[i])
				continue;
			double tmp=0;
			tmp=min(min(min(w[i][0]-xx1,xx2-w[i][0]),yy2-w[i][1]),w[i][1]-yy1);
			for (int j=0;j<n;j++)
			{
				if (!used[j])
					continue;
				double tp=0;
				tp=sqrt((w[i][0]-w[j][0])*(w[i][0]-w[j][0])+(w[i][1]-w[j][1])*(w[i][1]-w[j][1]));
				if (tp>q[j])
				{
					tp-=q[j];
					if (tp<tmp)
						tmp=tp;
				}
				else
				{
					tmp=0;
					break;
				}
			}
			used[i]=1;
			q[i]=tmp;
			temp+=pi*tmp*tmp;
			dfs(x+1);
			used[i]=0;
			q[i]=0;
			temp-=pi*tmp*tmp;
		}
	}
}