比赛 |
20120925 |
评测结果 |
AAAAAAAAAA |
题目名称 |
油滴扩展 |
最终得分 |
100 |
用户昵称 |
苏轼 |
运行时间 |
0.006 s |
代码语言 |
C++ |
内存使用 |
2.50 MiB |
提交时间 |
2012-09-25 20:20:40 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
const double pi=3.1415926;
int n;
double xx1,xx2,yy1,yy2;
double w[7][2]={0},q[7]={0};
bool used[7]={0};
double answer=0,temp=0;
void dfs(int x);
int main()
{
freopen ("oilbox.in","r",stdin);
freopen ("oilbox.out","w",stdout);
cin>>n>>xx1>>yy1>>xx2>>yy2;
if (xx1>xx2)
{
double tmp;
tmp=xx1;
xx1=xx2;
xx2=tmp;
}
if (yy1>yy2)
{
double tmp;
tmp=yy1;
yy1=yy2;
yy2=tmp;
}
for (int i=0;i<n;i++)
{
cin>>w[i][0]>>w[i][1];
}
dfs(0);
int ans=0;
if (((int)(answer*10)%10)<5)
{
ans=answer*10;
ans/=10;
}
else
{
ans=answer*10+10;
ans/=10;
}
cout<<((int)((int)(yy2-yy1)*(xx2-xx1))-ans);
return 0;
}
void dfs(int x)
{
if (x==n)
{
if (temp>answer)
answer=temp;
}
else
{
for (int i=0;i<n;i++)
{
if (used[i])
continue;
double tmp=0;
tmp=min(min(min(w[i][0]-xx1,xx2-w[i][0]),yy2-w[i][1]),w[i][1]-yy1);
for (int j=0;j<n;j++)
{
if (!used[j])
continue;
double tp=0;
tp=sqrt((w[i][0]-w[j][0])*(w[i][0]-w[j][0])+(w[i][1]-w[j][1])*(w[i][1]-w[j][1]));
if (tp>q[j])
{
tp-=q[j];
if (tp<tmp)
tmp=tp;
}
else
{
tmp=0;
break;
}
}
used[i]=1;
q[i]=tmp;
temp+=pi*tmp*tmp;
dfs(x+1);
used[i]=0;
q[i]=0;
temp-=pi*tmp*tmp;
}
}
}