题目描述

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

注：圆的面积公式V=pi*r*r，其中r为圆的半径。

输入格式

第1行一个整数N。

第2行为长方形边框一个顶点及其对角顶点的坐标，x,y,x’,y’。

接下去N行，每行两个整数xi,yi，表示盒子的N个点的坐标。

以上所有的数据都在[-1000，1000]内。

输出格式

一行，一个整数，长方形盒子剩余的最小空间（结果四舍五入输出）

输入输出样例

输入 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
2
20 0 10 10
13 3
17 7
输出 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
50

思路
　　枚举第 i 个油滴与边界和其他油滴之间的距离，枚举出面积最大的情况即可
CODE
#include  < bits/stdc++.h >
#define  dbg (x ) cout  << #x  <<  " = "  << x  << endl
#define  eps  1e - 8
#define  pi  acos (- 1.0 )

using  namespace  std ;
typedef  long  long LL ;

const  int inf  =  0x3f3f3f3f ;

template < class  T > inline  void  read ( T  &res )
{
     char c ;T flag = 1 ;
     while ((c = getchar ())< ' 0 ' ||c > ' 9 ' ) if (c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
     while ((c = getchar ())>= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}

namespace   _buff   {
     const   size_t  BUFF  =   1   <<   19 ;
     char  ibuf [ BUFF ],   * ib  =  ibuf ,   * ie  =  ibuf ;
     char   getc ()   {
         if   ( ib  ==  ie )   {
            ib  =  ibuf ;
            ie  =  ibuf  +   fread ( ibuf ,   1 ,  BUFF ,  stdin );
         }
         return  ib  ==  ie  ?   - 1   :   * ib ++;
     }
}

int  qread ()  {
     using  namespace  _buff ;
     int ret  =  0 ;
     bool pos  =  true;
     char c  =  getc ();
     for  (;  (c  <  ' 0 '  || c  >  ' 9 ' )  && c  !=  ' - ' ; c  =  getc ())  {
         assert (~ c );
     }
     if  (c  ==  ' - ' )  {
        pos  =   false;
        c  =   getc ();
     }
     for  (; c  >=  ' 0 '  && c  <=  ' 9 ' ; c  =  getc ())  {
        ret  =   ( ret  <<   3 )   +   ( ret  <<   1 )   +   ( c  ^   48 );
     }
     return pos  ? ret  :  -ret ;
}

const  int maxn  =  1e3  +  7 ;

int n ;

struct   node {
     double  x ,  y ;
     double  r ;
}  a [ maxn ];

bool vis [maxn ];
double dis [maxn ][maxn ];

double lx , rx , dy , uy ;
double area ;
double ans  =  0 ;

double  dist ( node a ,  node b )  {
     return  sqrt ((a .x  - b .x )  *  (a .x  - b .x )  +  (a .y  - b .y )  *  (a .y  - b .y ));
}

bool  check ( int id )  {
     if ((a [id ].x  - a [id ].r )  < lx  -  1  ||  (a [id ].x  + a [id ].r )  > rx  -  1  ||  (a [id ].y  - a [id ].r )  < dy  -  1  ||  (a [id ].y  + a [id ].r )  > uy  -  1 )  {
         return   false;
     }
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         if ( i  ==  id )
             continue ;
         else   {
             if ( dist (a [ i ],  a [ id ])   <  a [ i ].r   +  a [ id ].r   +   1 )   {
                 return   false;
             }
         }
     }
     return  true;
}

void  dfs ( int cnt ,  double sum )  {
     if (cnt  > n )  {
        ans  =   max ( ans ,  sum );
     }
    // dbg(ans);
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         if (!vis [ i ])   {
            a [ i ].r   =   min ( min (a [ i ].x   -  lx ,  rx  -  a [ i ].x ),
                          min (a [ i ].y   -  dy ,  uy  -  a [ i ].y ));     
             for   (   int  j  =   1 ;  j  <=  n ;   ++ j  )   {
                 if (vis [ j ])   {
                    a [ i ].r   =   min (a [ i ].r ,  dis [ i ][ j ]   -  a [ j ].r );
                 }
             }
            vis [ i ]   =   1 ;
             if (a [ i ].r   <   0 )   {
                a [ i ].r   =   0 ;
             }
             dfs ( cnt  +   1 ,  sum  +  a [ i ].r *a [ i ].r * pi );
            vis [ i ]   =   0 ;
         }
     }
     return ;
}

int  main ()
{
     read (n );
     scanf ( " %lf %lf %lf %lf " ,&lx ,  &dy ,  &rx ,  &uy );
     if (lx  > rx )  {
         swap ( lx ,  rx );
     }
     if (dy  > uy )  {
         swap ( dy ,  uy );
     }
    area  =  (rx  - lx )  *  (uy  - dy );
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         read (a [ i ].x );
         read (a [ i ].y );
     }
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         for   (   int  j  =  i  +   1 ;  j  <=  n ;   ++ j  )   {
            dis [ i ][ j ]   =  dis [ j ][ i ]   =   dist (a [ i ],  a [ j ]);
         }
     }
     dfs ( 1 ,  0.0 );
    // dbg(area);
    // dbg(ans);
     printf ( " %d\n " ,( int )(area  - ans  +  0.5 ));
     return  0 ;
}