比赛 20120925 评测结果 AAAAWWAAWA
题目名称 油滴扩展 最终得分 70
用户昵称 QhelDIV 运行时间 0.003 s
代码语言 C++ 内存使用 3.25 MiB
提交时间 2012-09-25 20:56:03
显示代码纯文本
#include <fstream>
#include <cstdlib>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream fin("oilbox.in");
ofstream fout("oilbox.out");
double Xmin,Xmax,Ymin,Ymax,X[100],Y[100];
double R[100],Sum,Max;
bool flag[10];
int N,X1,X2,Y1,Y2,order[100];
const double pi=3.1415926;
void Initialize()
{
	fin>>N;
	fin>>X1>>Y1>>X2>>Y2;
	Xmin=min(X1,X2);Xmax=max(X1,X2);
	Ymin=min(Y1,Y2);Ymax=max(Y1,Y2);
	for(int i=1;i<=N;i++)
		fin>>X[i]>>Y[i];
}
double Fig(int a,int b)
{
	return (X[a]-X[b])*(X[a]-X[b])+(Y[a]-Y[b])*(Y[a]-Y[b]);
}
void DFS(int pos)
{
int I;
	if(pos>N)
		Max=max(Max,Sum);
	for(int i=1;i<=N;i++)
		if(!flag[i])
		{
		int j;
			R[i]=min(Xmax-X[i],X[i]-Xmin);
			R[i]=min(R[i],Y[i]-Ymin);
			R[i]=min(R[i],Ymax-Y[i]);
			for(j=1;j<=N;j++)
				if(flag[j]==true)
					R[i]=min(R[i],sqrt(Fig(i,j))-R[j]);
			flag[i]=true;
		double rec=Sum;
			Sum+=R[i]*R[i]*pi;
			DFS(pos+1);
			R[i]=0;
			flag[i]=false;
			Sum=rec;
		}
}

int main()
{
	Initialize();
	
	DFS(1);
	
	fout<<setiosflags(ios::fixed)<<setprecision(0)<<(Xmax-Xmin)*(Ymax-Ymin)-Max<<endl;
	
	fin.close();
	fout.close();
	return 0;
}