题目描述

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

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

输入格式

第1行一个整数N。

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

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

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

输出格式

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

输入样例

20 0 10 10
13 3
17 7

输出样例

50

题解

思路：枚举所有放油滴顺序的全排列

1.油滴扩展时不能超出矩形的范围
2.油滴扩展时接触到其他油滴就停止
根据圆与点的位置关系，我们可以得出：

• 如果圆的半径大于点到圆心的距离，点在圆内，对于这种情况我们可以得出d−r<0，即新的油滴在其它油滴内部，无法进行扩展。
• 如果圆的半径等于点到圆心的距离，点在圆上，对于这种情况我们可以得出d−r=0，也无法进行扩展。
• 如果圆的半径小于点到圆心的距离，点在圆外，对于这种情况我们可以得出d−r>0，此时新油滴可以扩展，它的半径为r′=(d−r)，面积为$S=πr′^2$。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
#include<string>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> PII;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef long long LL;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;

const int N=10;
double xx1,yy1,xx2,yy2;
double x[N],y[N],r[N];
bool vis[N];
double ans;
int n;

double dist(double a,double b,double c,double d)
{
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}

double calc(int t)
{
    double s1=min(fabs(x[t]-xx1),fabs(y[t]-yy1));
    double s2=min(fabs(x[t]-xx2),fabs(y[t]-yy2));

    double ans=min(s1,s2);
    for(int i=0;i<n;i++)
        if(vis[i] && i!=t)
        {
            double d=dist(x[t],y[t],x[i],y[i]);
            ans=min(ans,max(d-r[i],0.0));
        }
    return ans;
}

void dfs(int u,double sum)
{
    if(u == n)
    {
        ans=max(ans,sum);
        return;
    }

    for(int i=0;i<n;i++)
        if(!vis[i])
        {
            r[i]=calc(i);
            vis[i]=1;
            dfs(u+1,sum+pi*r[i]*r[i]);
            vis[i]=0;
        }
}

int main()
{
    cin>>n;
    scanf("%lf%lf%lf%lf",&xx1,&yy1,&xx2,&yy2);

    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf",&x[i],&y[i]);
    }

    dfs(0,0);

    double rec=fabs(xx1-xx2)*fabs(yy1-yy2);
    printf("%.0f\n",rec-ans);
    // system("pause");
}