P1378 油滴扩展

时间：2021-11-13 21:57:09

题目描述

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

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

输入输出格式

输入格式：

第1行一个整数N。

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

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

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

输出格式：

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

输入输出样例

输入样例#1： 
2
20 0 10 10
13 3
17 7
输出样例#1： 
50

对于样例的理解，第一个油滴扩散半径为3，因为受矩形框的限制。第二个油滴扩散半径小于3，因为受第一个油滴的限制。r2受r1限制，即r2<=dis-r1. （dis为圆心距）

枚举n个点的先后顺序。对于第i个油滴，能扩散到的半径Ri只受矩形和前i-1个油滴半径的约束，为方便求Ri，可以先预处理出各个点之间的距离dis[i][j]。

//Gang
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define FOR(x,y,z) for(int x=y;x<=z;x++)
#define REP(x,y,z) for(int x=y;x>=z;x--)
#define ll long long
using namespace std;
int n;
][],x,y,x2,y2,a[][];
],r;//r为准备放置的油滴的扩散半径
double maxn;
];
);
void dfs(int steps,double s)//steps位当前步数，s为当前面积
{
    )
    {
        if(s>maxn)
            maxn=s;
    }
    else
        FOR(k,,n)
            if(!vis[k])
            {
                //矩形和已放置的油滴约束了r的大小
                r=fabs(y2-a[k][]);
                ]))r=fabs(y-a[k][]);
                ]))r=fabs(x2-a[k][]);
                ]))r=fabs(x-a[k][]);
                FOR(i,,n)
                {
                    if(vis[i])
                    {
                        if(r>dis[k][i]-R[i])r=dis[k][i]-R[i];
                    }
                }
                //注意r不能为负
                r=r<?:r;
                R[k]=r;
                vis[k]=;
                dfs(steps+,s+pi*r*r);
                vis[k]=;
                R[k]=0.0;

            }
}
int main()
{
    scanf("%d%lf%lf%lf%lf",&n,&x,&y,&x2,&y2);
    FOR(i,,n)scanf(],&a[i][]);
    FOR(i,,n)
    {
        FOR(j,,i)
        {
              //预处理出油滴间距dis
            dis[i][j]=sqrt(pow(fabs(a[i][]-a[j][]),)+pow(fabs(a[i][]-a[j][]),));
            dis[j][i]=dis[i][j];
        }
    }
    double S=fabs(x-x2)*fabs(y-y2);//矩形面积
    dfs(,0.0);
    printf("%.0lf",floor(S-maxn+0.5));
    ;
}

相关文章