luogu_1378 油滴扩展

#include <bits/stdc++.h>
using namespace std;
int n;
double x,xx,y,yy,ans,pi=3.141592,t[10];
bool use[10];
struct point{double x,y;}a[10];

double min(double x,double y){return x<=y?x:y;}
double max(double x,double y){return x>=y?x:y;}

double dist(int x,int y){
	double sum=sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
	return sum;
}

double maxx(int now){
	double maxn;
	maxn=min(min(xx-a[now].x,a[now].x-x),min(yy-a[now].y,a[now].y-y));
	for(int i=1;i<=n;i++)if(use[i])maxn=min(dist(now,i)-t[i],maxn);
	if(maxn<0)maxn=0;
	return maxn;
}

void dfs(int now,double sum){
	if(now==n){ans=max(ans,sum); return;}
	for(int i=1;i<=n;i++)if(!use[i]){
			double minn=maxx(i);
			t[i]=minn;
			minn=minn*minn*pi;
			use[i]=1;
			dfs(now+1,sum+minn);
			use[i]=0;
			t[i]=0;
		}
}

int main(){
	scanf("%d",&n);
	scanf("%lf%lf%lf%lf",&x,&y,&xx,&yy);
	if(y>yy){double g=y; y=yy; yy=g;}
	if(x>xx){double g=x; x=xx; xx=g;}
	for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
	dfs(0,0);
	int g=(xx-x)*(yy-y);
	ans=g-ans;
	if(ans-0.5>(double)((int)ans))printf("%d
",(int)ans+1);
	else printf("%d
",(int)ans);
	return 0;
}