题解-油滴扩展-深搜

思路

每个油滴点最大可扩散多少 受到两个条件 限制
1. 边框
2. 其他油滴
深搜得到油滴总共可扩展的最大值
答案即为 总面积 - 油滴扩展的总面积最大值

必要知识

• 两点间距离公式：用于求两个油滴间距离（代码中point_dis函数即用于此）

坑点

做这道题时要注意，最开始在计算过程中尽量用double类型
否则在计算结果时精度不够，导致四舍五入后的答案有偏差

代码如下

#include<bits/stdc++.h>
#define PI 3.1415926 //定义π
using namespace std ;

double a[101][2] , R[101] , m , dis[101][7];
int n , vis[101] , x , y , x2 , y2 ;

double point_dis(int x3,int y3,int x4,int y4){ //计算两点距离 
	return sqrt(pow(x3-x4,2) + pow(y3-y4,2)) ; //两点间距离公式
	//sqrt()：计算算术平方根  
	//pow()：计算次幂，此处用于计算平方 
}

double abss(double x){ //定义一个给浮点数取绝对值的函数
    return x > 0.0 ? x : -x ;
}

double radius(int i){ // 在该点到四个墙面的距离中取最小值 
	double r = abss(y2 - a[i][1]) ;
    if (r > abss(x2 - a[i][0]))
        r = abss(x2 - a[i][0]) ;
	if (r > abss(y - a[i][1]))
        r = abss(y - a[i][1]) ;
    if (r > abss(x - a[i][0]))
        r = abss(x - a[i][0]) ;
    return r ;
} 

void dfs(int cnt,double s){ // 放置第cnt个油滴，此时总油滴扩散面积为s 
	if(cnt == n + 1) m = s > m ? s : m ; //已经完成所有油滴的扩散，记录最大值m
	else
	{//没放完，继续算！ 
	for(int i = 1 ; i <= n ; i++){
		if(!vis[i]){
			double r = radius(i) ; //确定油滴可扩散的最小半径 
		 	for (int j = 1 ; j <= n ; j++)
                if (vis[j]){ //如果这个点有油滴
                    r = r > dis[i][j] - R[j] ? dis[i][j] - R[j] : r ;
                    // r需比两个油滴间的距离 - 另一个油滴的扩散距离小 
                }
            r = r < 0 ? 0 : r ; 
			//如果一个油滴已经覆盖了没有滴的油滴即r<0
			//那么r=0 
 
            vis[i] = 1 ; 
			R[i] = r ;
            dfs(cnt + 1, s + PI * r * r); //在下一层搜索时 把已有面积传入下层
            vis[i] = 0 ; 
			R[i] = 0.0 ;//返回上层 解除标记 并且让半径恢复0
		}
	}
	} 
}

int main(){
	
	cin >> n ;
	cin >> x >> y >> x2 >> y2 ; // 边界  
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i][0] >> a[i][1] ; // 输入该点x坐标和y坐标 
	}
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j < i ; j++){
			if(i != j) dis[i][j] = dis[j][i] = point_dis(a[i][0],a[i][1],a[j][0],a[j][1]) ;
			// 记录初始油滴点之间的距离 
		}
	} 
	dfs(1,0.0) ; 
	double S = abss(x - x2) * abss(y - y2) ; //大边框面积
    cout << int(S - m + 0.5) ; // 四舍五入 
	return 0 ;
} 

希望对你有所帮助！

如有问题请评论区指正