比赛 |
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;
}