【洛谷P1378】油滴扩展

搜索……

PS一个坑点：r<=0时并不是舍弃这种情况，而是让r=0

（因为每个点都要放一滴油）（读题啊！）

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #define dd double

 using namespace std;

 const int N=;

 const dd pai=3.1415926535,INF=;

 int flag[N],n;

 dd xx,yy,x2,y2,x[N],y[N];

 //'int y1' redeclared as different kind of symbol,保留字

 dd dx[N][],dy[N][],dis[N][N],r[N],ans;

 void swap(dd &a,dd &b){

     dd tmp=a;

     a=b;

     b=tmp;

 }

 dd min(dd a,dd b){

     return a<b?a:b;

 }

 dd max(dd a,dd b){

     return a>b?a:b;

 }

 void dfs(int step,dd size){

     if (step==n){

         ans=max(ans,size);

         return;

     }

     for (int i=;i<=n;i++){

         if (!flag[i]){

             dd len=min(dx[i][],dx[i][]);

             len=min(len,min(dy[i][],dy[i][]));

             for (int j=;j<=n;j++)

                 if (flag[j]){

                     dd l=dis[i][j]-r[j];

                     if (l>)

                         len=min(len,l);

                     else

                         len=;//***

                 }

             flag[i]=;

             r[i]=len;

             size+=pai*r[i]*r[i];

             dfs(step+,size);

             flag[i]=;

             size-=pai*r[i]*r[i];

         }

     }

 }

 int main(){

     scanf("%d",&n);

     scanf("%lf %lf %lf %lf",&xx,&yy,&x2,&y2);

     for (int i=;i<=n;i++)

         scanf("%lf %lf",&x[i],&y[i]);

     if (xx>x2)

         swap(xx,x2);

     if (yy>y2)

         swap(yy,y2);

     for (int i=;i<=n;i++){

         dx[i][]=x2-x[i];

         dx[i][]=x[i]-xx;

         dy[i][]=y2-y[i];

         dy[i][]=y[i]-yy;

         for (int j=;j<=n;j++){

             int cx=x[i]-x[j];

             int cy=y[i]-y[j];

             dis[i][j]=sqrt(cx*cx+cy*cy);

         }

     }

     ans=;

     dfs(,);

     dd s=(x2-xx)*(y2-yy)-ans;

     int S=s+0.5;

     printf("%d",S);

     return ;

 }

STD