10分求条
查看原帖
10分求条
1074937
zhouchangze楼主2025/1/22 20:05
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=10,pi=3.1415926535;
int n,xa,ya,xb,yb,dx[N],dy[N];
double r[N],ans;
bool st[N];
double cal(int i){
	double res=min(min(abs(dx[i]-xa),abs(dx[i]-xb)),min(abs(dy[i]-ya),abs(dy[i]-yb)));
	for (int j=1;j<=n;j++)
		if (i!=j&&st[j]){
			double d=sqrt((dx[i]-dx[j])*(dx[i]-dx[j])+(dy[i]-dy[j])*(dy[i]-dy[j]));
			res=min(res,d-r[j]);
		}
	return res;
}
void dfs(double sum,int step){
	if (step>n){
		ans=max(ans,sum);
		return;
	}
	for (int i=1;i<=n;i++)
		if (!st[i]){
			r[i]=cal(i);
			st[i]=true;
			dfs(sum+pi*r[i]*r[i],step+1);
			st[i]=false;
		}
	return;
}
int main(){
	scanf("%d",&n);
	scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
	for (int i=1;i<=n;i++) scanf("%d%d",&dx[i],&dy[i]);
	dfs(0.0,1);
    printf("%d\n",int(abs(xa-xb)*abs(ya-yb)-ans+0.5));
	return 0;
}
2025/1/22 20:05
加载中...