10分
查看原帖
10分
679600
quruijie5418814524楼主2022/11/17 17:03
#include<bits/stdc++.h>
using namespace std;
bool vis[15];
double x[15],y[15],r[15],xa,ya,xb,yb,ansmax;
int n;
int const PI=3.14;
double cal(int i){
	double s1=min(abs(x[i]-xa),abs(x[i]-xb));
	double s2=min(abs(y[i]-ya),abs(y[i]-yb));
	double ans=min(s1,s2);
	for(int j=1;j<=n;j++){
		if(i!=j&&vis[j]){
			double d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			ans=min(ans,max(d-r[j],0.0));
		}
	}
	return ans;
}
void dfs(int dep,double sum){
	if(dep>n){
		ansmax=max(ansmax,sum);
		return;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			r[i]=cal(i);
			vis[i]=1;
			dfs(dep+1,sum+r[i]*r[i]*PI);
			vis[i]=0;
		}
	}
}
int main(){
	double ss;
	cin>>n;
	cin>>xa>>ya>>xb>>yb;
	ss=abs(xa-xb)*abs(ya-yb);
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]; 
	}
	dfs(1,0);
	printf("%d",int(ss-ansmax+0.5));
	return 0;
}
2022/11/17 17:03
加载中...