比赛 |
20120925 |
评测结果 |
AAAAWWAAWA |
题目名称 |
油滴扩展 |
最终得分 |
70 |
用户昵称 |
QhelDIV |
运行时间 |
0.003 s |
代码语言 |
C++ |
内存使用 |
3.25 MiB |
提交时间 |
2012-09-25 20:56:03 |
显示代码纯文本
#include <fstream>
#include <cstdlib>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream fin("oilbox.in");
ofstream fout("oilbox.out");
double Xmin,Xmax,Ymin,Ymax,X[100],Y[100];
double R[100],Sum,Max;
bool flag[10];
int N,X1,X2,Y1,Y2,order[100];
const double pi=3.1415926;
void Initialize()
{
fin>>N;
fin>>X1>>Y1>>X2>>Y2;
Xmin=min(X1,X2);Xmax=max(X1,X2);
Ymin=min(Y1,Y2);Ymax=max(Y1,Y2);
for(int i=1;i<=N;i++)
fin>>X[i]>>Y[i];
}
double Fig(int a,int b)
{
return (X[a]-X[b])*(X[a]-X[b])+(Y[a]-Y[b])*(Y[a]-Y[b]);
}
void DFS(int pos)
{
int I;
if(pos>N)
Max=max(Max,Sum);
for(int i=1;i<=N;i++)
if(!flag[i])
{
int j;
R[i]=min(Xmax-X[i],X[i]-Xmin);
R[i]=min(R[i],Y[i]-Ymin);
R[i]=min(R[i],Ymax-Y[i]);
for(j=1;j<=N;j++)
if(flag[j]==true)
R[i]=min(R[i],sqrt(Fig(i,j))-R[j]);
flag[i]=true;
double rec=Sum;
Sum+=R[i]*R[i]*pi;
DFS(pos+1);
R[i]=0;
flag[i]=false;
Sum=rec;
}
}
int main()
{
Initialize();
DFS(1);
fout<<setiosflags(ios::fixed)<<setprecision(0)<<(Xmax-Xmin)*(Ymax-Ymin)-Max<<endl;
fin.close();
fout.close();
return 0;
}