洛谷P1378 油滴扩展 题解

题目链接：P1378 油滴扩展

题意：

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

注：圆的面积公式 $V=\pi r^2$，其中 $r$ 为圆的半径。

对于 $100\%$ 的数据，$1\le N\le 6$，坐标范围在 $[-1000,1000]$ 内。

数据范围告诉我们这就是一道暴搜题

枚举油滴扩展的顺序，然后和已经扩散好的油滴算一下距离

注意距离可能为负，此时新油滴在某油滴内部，此时认为 $r=0$ 即可

最后的答案就是总面积减去油滴面积并

时间复杂度 $O(n\times n!)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(15)
const double pi = 3.14159265354;
int n,vis[N];
double xa,ya,xb,yb,x[N],y[N],S,mx,r[N];
#define pf(x) ((x)*(x))
double dis(int i,int j)
{
    return sqrt(pf(x[i]-x[j])+pf(y[i]-y[j]));}
double cal(int i)
{
    
    double l1=min(abs(x[i]-xa),abs(x[i]-xb));
    double l2=min(abs(y[i]-ya),abs(y[i]-yb));
    double res=min(l1,l2);
    for(int j=1; j<=n; j++)
        if(i!=j&&vis[j])
        {
    
            double d=dis(i,j);
            res=fmin(res,max(d-r[j],0.0));
        }
    return res;
}
void dfs(int k,double sum)
{
    
    if(k>n)
    {
    
        mx=max(mx,sum);
        return;
    }
    for(int i=1; i<=n; i++)
    {
    
        if(!vis[i])
        {
    
            r[i]=cal(i);
            vis[i]=1;
            dfs(k+1,sum+r[i]*r[i]*pi);
            vis[i]=0;
        }
    }
}
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> xa >> ya >> xb >> yb;
    S=abs((xa-xb)*(ya-yb));
    for(int i=1; i<=n; i++)
        cin >> x[i] >> y[i];
    dfs(1,0);
    cout << fixed << setprecision(0);
    cout << S-mx << endl;
    return 0;
}

转载请说明出处