比赛 20120925 评测结果 AAAAAAAAAA
题目名称 油滴扩展 最终得分 100
用户昵称 临轩听雨ゐ 运行时间 0.006 s
代码语言 C++ 内存使用 2.82 MiB
提交时间 2012-09-25 20:18:53
显示代码纯文本
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
 
int n;
double x[6],y[6],r[6];
double a0,b0,a1,b1,v=0.0;
bool hash[6];
double pi=3.141592653;

void work(int i)
{
	r[i]=1000000.0;
	for (int j=0; j<n; j++)
		if (i!=j && hash[j])
		{
			double nn=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			r[i]=min(r[i],max(0.0,nn-r[j]));
		}
	r[i]=min(r[i],abs(x[i]-a0));
	r[i]=min(r[i],abs(x[i]-a1));
	r[i]=min(r[i],abs(y[i]-b0));
	r[i]=min(r[i],abs(y[i]-b1));
 }
 
void dfs(int t)
{
	if (t>=n)
	{
		double sum=0.0;
		for (int i=0; i<n; i++)
			sum+=pi*r[i]*r[i];
		v=max(v,sum);
		return;
	}
	for (int i=0; i<n; i++)
		if (!hash[i])
		{
			hash[i]=1;
			work(i);
			dfs(t+1);
			hash[i]=0;
			r[i]=0;
		}
 }
 
int main()
{
    ifstream in("oilbox.in");
    ofstream out("oilbox.out");
    in>>n;
    in>>a0>>b0>>a1>>b1;
    for (int i=0; i<n; i++)
        in>>x[i]>>y[i];
    dfs(0);
    double ans=abs(a0-a1)*abs(b0-b1)-v;
		out<<setiosflags(ios::fixed)<<setprecision(0)<<ans<<endl;
	return 0;
}