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