社区讨论

0pts

P1378油滴扩展参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lymp8s5e
此快照首次捕获于
2024/07/15 16:05
2 年前
此快照最后确认于
2024/07/15 16:50
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
#define double long double
using namespace std;
double n,x1,x2,y6,y2,p[10],q[10],r[10],ans,xm,ym,xn,yin;
bool vis[10];
double s(int k){
	return k*k*3.1415926;
}
double dis(double x3,double y3,
		   double x4,double y4){
	return sqrt((x3-x4)*(x3-x4)+
		        (y3-y4)*(y3-y4));
}
double f(double x,double y,int k){
	double res=0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		if(vis[i]&&i!=k){
			if(dis(x,y,p[i],q[i])-r[i]<0){
				res=0;
				break;
			}
			res=min(res,dis(x,y,p[i],q[i])-r[i]);
		}
	}
	return res;
}
void dfs(int u,double w){
	if(u>n){
		ans=max(w,ans);
	}	
	for(int i=u;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			r[i]=min(min(p[i]-xn,xm-p[i]),min(q[i]-yin,ym-q[i]));
			r[i]=min(r[i],f(p[i],q[i],i));
			dfs(i,w+s(r[i]));
			vis[i]=0;
			r[i]=0;
		}
	}
}
int main(){
	cin>>n>>x1>>y6>>x2>>y2;
	xm=max(x1,x2);
	xn=min(x1,x2);
	yin=min(y6,y2);
	ym=max(y6,y2);
	for(int i=1;i<=n;i++){
		cin>>p[i]>>q[i];
	}
	dfs(1,0);
	double s1=abs((x1-x2)*(y6-y2));
	cout<<(int)(s1-ans);
}

回复

1 条回复,欢迎继续交流。

正在加载回复...