90pts求助
查看原帖
90pts求助
1092973
zhangjyoi楼主2024/7/22 15:02
#include<bits/stdc++.h>
using namespace std;
int n;
int a,b,c,d;
vector<int>x,y,t,r;
double dist(int p,int q,int r,int s){
	return sqrt(1.0*(p-r)*(p-r)+1.0*(q-s)*(q-s));
} 
int main(){
	cin>>n;
	x.resize(n);
	y.resize(n);
	t.resize(n);
	r.resize(n);
	cin>>a>>b>>c>>d;
	double sum=fabs(a-c)*fabs(b-d);
	for(int i=0;i<n;i++)cin>>x[i]>>y[i];
	for(int i=0;i<n;i++)t[i]=i;
	double maxn=0;
	do{
		double cnt=0;
		for(int i=0;i<n;i++){
			double minn=1e9;
			for(int j=0;j<i;j++){
				minn=min(minn,dist(x[t[i]],y[t[i]],x[t[j]],y[t[j]])-r[t[j]]);
			}
			minn=min(minn,fabs(x[t[i]]-a));
			minn=min(minn,fabs(x[t[i]]-c));
			minn=min(minn,fabs(y[t[i]]-b));
			minn=min(minn,fabs(y[t[i]]-d));
			if(minn<0)minn=0;
			r[t[i]]=minn;
			cnt+=3.1415926535*minn*minn;
		}
		maxn=max(cnt,maxn);
	}while(next_permutation(t.begin(),t.end()));
	printf("%.0lf",round(sum-maxn));
	return 0;
}
2024/7/22 15:02
加载中...