题解 P1378 【油滴扩展】

· · 题解

暴力

主要思想是在dfs过程中维护以下几个值

那么dfs函数就可以写出来了 dfs（k,ret）表示当前正在布置第k个油滴，框子里已经占据了ret的面积

dfs时用长方形框子的四条边和之前其他的油滴的位置来找到最大的扩散半径深搜即可

并且需要注意一下如果存在一个油滴使得此时放置的油滴圆心与该油滴圆心距离小于等于该油滴扩散半径，那么就说明此时放置的油滴位置已被覆盖

最后输出答案使用round函数取四舍五入值

一些其他的小细节都在代码注释里

AC代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
double pi=3.1415926535897932;
int n;
double xa,xb,ya,yb,ans,S;
bool vst[7];
struct p
{
    double x,y;
}poi[7];//存储油滴
struct a
{
    double posx,posy,r;
}c[10];//存储已放置的油滴的位置和扩散半径
inline double dis(double ax,double ay,double bx,double by)
{
    return sqrt(pow(ax-bx,2)+pow(ay-by,2));
}
inline double s(double rr)
{
    return pi*rr*rr;
}
void dfs(int k,double ret)
{
    if(ret>S)
        return;
    if(k>=n+1)//此时油滴已经放完，更新被覆盖的最大面积
    {
        ans=max(ans,ret);
        return;
    }
    else
        for(int i=1;i<=n;i++)
        {
            double minn=1<<30;
            if(!vst[i])//vst表示油滴是否被放置过
            {
                for(int j=1;j<k;j++)//遍历之前的油滴
                {
                    double range=dis(c[j].posx,c[j].posy,poi[i].x,poi[i].y)-c[j].r;
                    if(range>=0)//当前油滴位置不在已被覆盖的面积上
                        minn=min(minn,range);
                    else//当前油滴的位置已被覆盖
                        minn=0;
                }
                minn=min(minn,xb-poi[i].x);
                minn=min(minn,poi[i].x-xa);
                minn=min(minn,yb-poi[i].y);
                minn=min(minn,poi[i].y-ya);//不要忘记用框子的四条边更新最大扩散半径
                c[k].posx=poi[i].x;
                c[k].posy=poi[i].y;
                c[k].r=minn;
                vst[i]=true;
                dfs(k+1,ret+s(minn));
                vst[i]=false;
                c[k].posx=c[k].posy=c[k].r=0;
            }
        }
}
int main()
{
    scanf("%d%lf%lf%lf%lf",&n,&xa,&ya,&xb,&yb);
    if(xa>xb)//使xb总大于xa
        swap(xa,xb);
    if(ya>yb)//同理
        swap(ya,yb);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&poi[i].x,&poi[i].y);
    S=(xb-xa)*(yb-ya);//框子的总面积
    for(int i=1;i<=n;i++)
        dfs(1,0);//放置第一个油滴，框子内被占据的面积是0
    printf("%.0lf",round((S-ans)));//总面积-覆盖面积=剩余面积
    //珂朵莉是我的
    return 0;
}