求助,第八个点过不去
查看原帖
求助,第八个点过不去
1015805
xiao__xiao楼主2023/7/2 19:33
#include<bits/stdc++.h>
using namespace std;
#define PI 3.1415926
double n ,x ,y ,xx ,yy ,flat[10]; //标记数组是否被选中过 
double r[10] ,minn = 0;//数组r记录半径 ,记录前几个点坐标 
struct zuobiao{
	double xi ,yi ,r ;
}z[10] ,zb[10];
void dfs(int x){//搜索 
	if(x>n){
		double sum = 0 ,bj ;//bj为最小半径 
		for(int i=1;i<=n;i++){
				bj = zb[i].r;
			for(int j=1;j<i;j++){
				double m =(double)(zb[j].xi-zb[i].xi)*(zb[j].xi-zb[i].xi)+(double)(zb[j].yi-zb[i].yi)*(zb[j].yi-zb[i].yi);
				double c = (double)sqrt(m) - zb[j].r;
				if(c>0)bj = (double)min(bj,c); //取到半径最小值 
				else 	bj = 0;
			}
			sum+=(double)PI*bj*bj;
		}
		minn = max(minn,sum);//求油滴面积的最大值 
		return;
	}
	for(int i=0;i<n;i++)
		if(flat[i]==0){
			flat[i]=1;
			zb[x].xi = z[i].xi ,zb[x].yi = z[i].yi ,zb[x].r = z[i].r;
			dfs(x+1);
			flat[i]=0;
		}
}

int main(){
	int ans;
	double delt ;
	cin >> n >> x >> y >> xx >> yy ;
	for(int i=0;i<n;i++){
		double a ,b ;
		cin >> z[i].xi >> z[i].yi ;
		a = (double)min((double)abs((double)xx-z[i].xi),(double)abs((double)x- z[i].xi));
		b = (double)min((double)abs((double)yy-z[i].yi),(double)abs((double)y- z[i].yi));
		z[i].r = (double)min((double)a,(double)b);//计算边界距离 
	}
	dfs(1);
	delt = abs((double)xx-x)*abs((double)yy-y);
	ans =round(delt - minn);
	cout << ans;
}
2023/7/2 19:33
加载中...