比赛 20120925 评测结果 AAAAAAAAAA
题目名称 油滴扩展 最终得分 100
用户昵称 TBK 运行时间 0.006 s
代码语言 C++ 内存使用 17.27 MiB
提交时间 2012-09-25 20:03:51
显示代码纯文本
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <algorithm>
#define MAXN 0x7fffffff
#define pie 3.1415926
using namespace std;
int a[2200][2200],b,c,d,l,m,n,k[6][2];
double r[6][2],s,t;
bool bo[6];
double ab(int x)
{
	return x>0?x:-x;
}
void DFS(int x)
{
	int i,j;
	double y,z;
	if (x==b)
	{
		z=0;
		for (i=0;i<x;i++) z+=(r[i][1]*r[i][1]*pie);
		if (z>s) s=z;
		return;
	}
	for (i=0;i<b;i++)
		if (bo[i]==false)
		{
			bo[i]=true;
			y=MAXN;
			for (j=0;j<x;j++)
			{
				z=sqrt((double)((k[(int)r[j][0]][0]-k[i][0])*(k[(int)r[j][0]][0]-k[i][0])+(k[(int)r[j][0]][1]-k[i][1])*(k[(int)r[j][0]][1]-k[i][1])));
				if (z-r[j][1]>=0) y=y>z-r[j][1]?z-r[j][1]:y;
					else y=0;
			}
			z=(double)ab(k[i][0]-c);
			y=y>z?z:y;
			z=(double)ab(k[i][1]-d);
			y=y>z?z:y;
			z=(double)ab(l-k[i][0]);
			y=y>z?z:y;
			z=(double)ab(m-k[i][1]);
			y=y>z?z:y;
			r[x][0]=(double)i;
			r[x][1]=y;
			DFS(x+1);
			bo[i]=false;
		}
}
int main(void)
{
	freopen ("oilbox.in","r",stdin);
	freopen ("oilbox.out","w",stdout);
	scanf("%d%d%d%d%d",&b,&c,&d,&l,&m);
	c+=1000;
	d+=1000;
	l+=1000;
	m+=1000;
	t=ab(l-c)*ab(m-d);
	for (n=0;n<b;n++) 
	{
		scanf("%d%d",&k[n][0],&k[n][1]);
		k[n][0]+=1000;
		k[n][1]+=1000;
	}
	DFS(0);
	printf("%.0lf",t-s);
	fclose(stdin);
	fclose(stdout);
	return 0;
}