比赛 20120925 评测结果 AAAAAAAAAA
题目名称 油滴扩展 最终得分 100
用户昵称 Makazeu 运行时间 0.004 s
代码语言 C++ 内存使用 2.11 MiB
提交时间 2012-09-25 19:44:34
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN=10;
const double PI=3.1415926;
int N,xa,ya,xb,yb,X[MAXN],Y[MAXN];
int Num[MAXN];double Ans=0;

inline double Min(double a,double b){return a<b?a:b;}
inline double Abs(double a) {return a>0?a:-a;}

inline void Check()
{
	double R[MAXN],Res=0,Now=0,Tmp,Dist;
	for(int i=1;i<=N;i++) R[i]=double(0);
	for(int i=1;i<=N;i++)
	{
		Now=1e12; 
		Tmp=Abs(double(X[Num[i]]-xa));  Now=Min(Now,Tmp);
		Tmp=Abs(double(X[Num[i]]-xb));  Now=Min(Now,Tmp);
		Tmp=Abs(double(Y[Num[i]]-ya));   Now=Min(Now,Tmp);
		Tmp=Abs(double(Y[Num[i]]-yb));   Now=Min(Now,Tmp);
		for(int j=1;j<=i-1;j++)
		{
			Dist=double(  (X[Num[i]]-X[Num[j]])*(X[Num[i]]-X[Num[j]])+(Y[Num[i]]-Y[Num[j]])*(Y[Num[i]]-Y[Num[j]]));
			Dist=sqrt(Dist)-R[j]; if(Dist<0) Dist=0; Now=Min(Now,Dist);
		} R[i]=Now;  Res+=Now*Now*PI;
	} if(Res>Ans) Ans=Res;
}

int main()
{
	freopen("oilbox.in","r",stdin);
	freopen("oilbox.out","w",stdout);
	scanf("%d\n%d %d %d %d\n",&N,&xa,&ya,&xb,&yb);
	for(int i=1;i<=N;i++) scanf("%d %d\n",&X[i],&Y[i]);
	for(int i=1;i<=N;i++) Num[i]=i; Check();
	while(next_permutation(Num+1,Num+N+1)) Check();Check();
	double Tot=Abs(double(xa-xb))*Abs(double(ya-yb));
	printf("%.0lf\n",(Tot-Ans));
	return 0;
}