20分,求助
  • 板块P1378 油滴扩展
  • 楼主Smg18
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/11 09:41
  • 上次更新2023/11/2 14:32:04
查看原帖
20分,求助
529017
Smg18楼主2023/10/11 09:41
#include<bits/stdc++.h>
using namespace std;
#define re register
#define pii pair<int,int>
const int N=1005,inf=1<<31;

int n;
double x,y,xx,yy;

pair<double,double> a[N];

double r[N];
double ans;
bool vis[N];
inline double calc(int t){
	double res=min(abs(a[t].first-x),abs(a[t].first-xx));
	res=min(abs(a[t].second-y),abs(a[t].second-yy));
	for(re int i=1;i<=n;i++){
		if(i==t||!vis[i])
			continue;
		
		int t1=a[i].first,t2=a[i].second;
		double d=sqrt(
		(a[t].first-t1)*(a[t].first-t1)+
		(a[t].second-t2)*(a[t].second-t2));
		
		res=min(res,max(d-r[i],0.0));
	}
	return res;
}
inline void dfs(int t,double sum){
	if(t==n+1){
		ans=max(ans,sum);
		return ;
	}
	for(re int i=1;i<=n;i++){
		if(!vis[i]){
			r[i]=calc(i);
			vis[i]=1;
			dfs(i+1,sum+r[i]*r[i]*3.14159265358979323846);
			vis[i]=0;
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>x>>y>>xx>>yy;
	for(re int i=1;i<=n;i++)
		cin>>a[i].first>>a[i].second;
	
	dfs(1,0);
	
	printf("%d\n",int(abs(x-xx)*abs(y-yy)-ans+0.5));
	
	return 0;
}
2023/10/11 09:41
加载中...