https://www.luogu.com.cn/problem/P1378

P1378 油滴扩展

题目描述

在一个长方形框子里，最多有 个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这 个点上放置油滴，才能使放置完毕后所有油滴占据的总面积最大呢？（不同的油滴不会相互融合）

注：圆的面积公式 ，其中 为圆的半径。

输入格式

第一行，一个整数 。

第二行，四个整数 ，表示长方形边框一个顶点及其对角顶点的坐标。

接下来 行，第 行两个整数 ，表示盒子内第 个点的坐标。

输出格式

一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）。

输入输出样例 #1

输入 #1

2
20 0 10 10
13 3
17 7

输出 #1

50

说明/提示

对于 的数据，，坐标范围在 内。

代码：

import sys
input=sys.stdin.readline
n=int(input())
a,b,c,d=map(int,input().split())
x=[]
y=[]
r=[0]*n
max_ans=0
for i in range(n):
    x_a,y_a=map(int,input().split())
    x.append(x_a)
    y.append(y_a)
bool1=[0]*n
def cul(i,r,x,y):
    global a,b,c,d,n
    min_dis=1e10
    min_r=1e10
    for j in range(0,n):

        if i!=j and bool1[j]==1 :
            min_r=min(((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5-r[j],min_r)
    min_dis=min(abs(a-x[i]),abs(c-x[i]),abs(b-y[i]),abs(d-y[i]),min_dis)
    min_r=min(max(min_r,0),min_dis)
    return min_r,3.1415926535*min_r**2

def dfs(k,ans):
    global n ,bool1,x,y,max_ans,r
    
    if k>=n:
        max_ans=max(ans,max_ans)
        return
    for j in range(n):
        if (1-bool1[j]):
            r[j],s=cul(j,r,x,y)
            bool1[j]=1
            dfs(k+1,ans+s)
            bool1[j]=0
dfs(0,0)
print(round(abs(a-c)*abs(b-d)-max_ans))

题解：

这道题是枚举，DFS。

关键是DFS的递归怎么写，分析题目，发现是所有情况为全排列，使用选择法，已选的圆形给上标记用s[ ]数组记录，dfs函数结束，再消除标记。

另外，要注意的精度问题，要取多一点位数。