60分求助,哪位大佬可以帮帮我呢?
查看原帖
60分求助,哪位大佬可以帮帮我呢?
658786
STUDENT00楼主2022/9/3 19:35

代码很好理解的^_^:

#include<bits/stdc++.h>
#define min(a,b) (a<b?a:b)
#define y1 y1_
#define pi 3.1416
using namespace std;
int n,x1,y1,x2,y2,x,y,a,b,xx[10],yy[10];
bool vis[10];
double ans,rr[10];
void dfs(int k,int s,double sum){
	double r=min(min(xx[k]-x,yy[k]-y),min(x+a-xx[k],y+b-yy[k]));
	for(int i=1;i<=n;i++){
		if(vis[i]&&i!=k) r=min(r,sqrt((xx[k]-xx[i])*(xx[k]-xx[i])+(yy[k]-yy[i])*(yy[k]-yy[i]))-rr[i]);
	}
	rr[k]=r;
	sum+=pi*r*r;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			dfs(i,s+1,sum);
			vis[i]=0;
		}
	}
	ans=max(ans,sum);
}
int main(){
	scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2);
	for(int i=1;i<=n;i++) scanf("%d%d",&xx[i],&yy[i]);
	x=min(x1,x2);
	y=min(y1,y2);
	a=abs(x1-x2);
	b=abs(y1-y2);
	for(int i=1;i<=n;i++){
		vis[i]=1;
		dfs(i,0,0);
		vis[i]=0;
	}
	printf("%.0lf",a*b-ans);
	return 0;
}
2022/9/3 19:35
加载中...