比赛 |
20120925 |
评测结果 |
WWWAAWWWAA |
题目名称 |
油滴扩展 |
最终得分 |
40 |
用户昵称 |
Truth.Cirno |
运行时间 |
0.004 s |
代码语言 |
C++ |
内存使用 |
2.11 MiB |
提交时间 |
2012-09-25 21:54:28 |
显示代码纯文本
#include <cstdio>
#include <cmath>
//#include <memory.h>
using namespace std;
const double PI=3.1415926;
int n,rec[10];
double a1,b1,a2,b2,ao[10],bo[10],r[10],maxsqu;
bool used[10];
double mtzdou(double a)
{
if (a<0)
return(0);
return(a);
}
double absdou(double a)
{
if(a<0)
return(-a);
return(a);
}
double mindou(double a,double b)
{
if (a>b)
return(b);
return(a);
}
double maxdou(double a,double b)
{
if (a<b)
return(b);
return(a);
}
void work(void)
{
int i,j,pi,pj;
double rt,squ=0;
// memset(r,0,sizeof(r));
for (i=1;i<=n;i++)
{
pi=rec[i];
rt=mindou(mtzdou(ao[pi]-a1),mtzdou(bo[pi]-b1));
rt=mindou(rt,mtzdou(a2-ao[pi]));
rt=mindou(rt,mtzdou(b2-bo[pi]));
for (j=1;/*j<=n*/j<i;j++)
{
// if (j==i)
// continue;
pj=rec[j];
rt=mindou(rt,absdou(mtzdou(sqrt((ao[pj]-ao[pi])*(ao[pj]-ao[pi])+(bo[pj]-bo[pi])*(bo[pj]-bo[pi]))-r[pj])));
}
r[pi]=rt;
squ+=rt*rt*PI;
}
maxsqu=maxdou(maxsqu,squ);
}
void dfs(int deep)
{
if (deep>n)
{
work();
return;
}
int i;
for (i=1;i<=n;i++)
if (!used[i])
{
used[i]=true;
rec[deep]=i;
dfs(deep+1);
// rec[deep]=0;
used[i]=false;
}
}
int main(void)
{
freopen("oilbox.in","r",stdin);
freopen("oilbox.out","w",stdout);
int i;
scanf("%d",&n);
scanf("%lf%lf%lf%lf",&a1,&b1,&a2,&b2);
for (i=1;i<=n;i++)
scanf("%lf%lf",&ao[i],&bo[i]);
dfs(1);
printf("%.0lf\n",(a2-a1)*(b2-b1)-maxsqu);
return(0);
}