洛谷1378 油滴扩展 dfs进行回溯搜索

题目链接：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);

  }