题目链接：https://www.luogu.com.cn/problem/P1378
题目中给出矩形的长宽和一些点，可以在每个点放油滴，油滴会扩展，直到触碰到矩形的周边或者其他油滴的边缘，求出剩余面积的最小值，就是求油滴面积的最大值。策略是dfs加上回溯，暴力求解。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define pi 3.14159265
#define prime2 1e9+9
#define scand(x) scanf("%lf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define pb(i) push_back(i)
#define ppb(x) pop_back(x)
#define inf 0x3f3f3f3f
#define maxn 10
int n;
double x1,x2,Y1,y2;//瞄的，y1洛谷编译不了
bool vis[maxn];
double dis[maxn][maxn],area=0.0;
struct p{
double x,y;
double r;
}cir[maxn];
double distance(double x1,double Y1,double x2,double y2)//点距
{
return sqrt((x1-x2)*(x1-x2)+(Y1-y2)*(Y1-y2));
}
double get_max(int num)//计算第num个点形成圆的最大半径
{
double tmp1=min(fabs(cir[num].x-x1),fabs(x2-cir[num].x));
double tmp2=min(fabs(cir[num].y-Y1),fabs(y2-cir[num].y));
double ans=min(tmp1,tmp2);
f(i,,n)
{
if((i!=num)&&vis[i])
{
if(dis[i][num]<=cir[i].r)return 0.0;//一旦被包围在内就不可以扩散
ans=min(ans,dis[i][num]-cir[i].r);
}
}
return ans;
}
void dfs(int dep,double tot)
{
if(dep==n)
{
//dbg(area);
area=max(area,tot);
return;
}
f(i,,n)
{
if(!vis[i])
{
vis[i]=true;
double R=get_max(i);
cir[i].r=R;
dfs(dep+,tot+pi*R*R);
vis[i]=false;
cir[i].r=0.0;//回溯
} }
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
scan(n);
scanf("%lf %lf %lf %lf",&x1,&Y1,&x2,&y2);
f(i,,n)
{
scand(cir[i].x);
scand(cir[i].y);
}
mem(vis,false);
f(i,,n)
f(j,,n)
{
dis[i][j]=distance(cir[i].x,cir[i].y,cir[j].x,cir[j].y);
}
dfs(,0.0);
int ans=(fabs(x1-x2)*fabs(Y1-y2)-area+0.5);
pf("%d\n",ans);
}