洛谷 P1378 油滴扩展 改错

P1378 油滴扩展

题目描述

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

输入输出格式

输入格式：

第1行一个整数N。

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

接下去\(N\)行，每行两个整数\(x_i,y_i\)，表示盒子的\(N\)个点的坐标。

以上所有的数据都在\([-1000,1000]\)内。

输出格式：

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

---

爆搜一下即可，这个幽默的数据。

然而，它居然问的是最小空间！！！！

我输出了最大面积。。。。

而且样例给的最小空间居然等于最大面积，绝对故意的。。。

---

code：

#include <cstdio>

#include <cmath>

const int N=7;

const double pi=3.1415926;

int up,ri,le,dow,x[N],y[N],n;

double fmax(double a,double b) {return a>b?a:b;}

double fmin(double a,double b) {return a<b?a:b;}

int min(int a,int b) {return a<b?a:b;}

int abs(int a) {return a>0?a:-a;}

int used[N];

double yuan[N],ans=0,dis[N][N];//圆的半径

double get(int a,int b)

{

    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));

}

void init()

{

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

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

            dis[i][j]=get(i,j);

}

double get(int id)

{

    double rm=1e300;

    rm=min(min(x[id],ri-x[id]),min(y[id],up-y[id]));

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

        if(yuan[i]!=0)

            rm=fmin(dis[id][i]-yuan[i],rm);

    return fmax(0.0,rm);

}

void dfs(int dep)

{

    if(dep==n+1)

    {

        double sum=0;

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

            sum+=yuan[i]*yuan[i]*pi;

        ans=fmax(sum,ans);

        return;

    }

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

        if(!used[i])

        {

            used[i]=1;

            yuan[i]=get(i);

            dfs(dep+1);

            yuan[i]=0.0;

            used[i]=0;

        }

}

int main()

{

    int x1,y1,x2,y2;

    scanf("%d",&n);

    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

    up=abs(y1-y2),ri=abs(x1-x2);

    le=min(x1,x2),dow=min(y1,y2);

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

    {

        scanf("%d%d",x+i,y+i);

        x[i]-=le,y[i]-=dow;

    }

    init();

    dfs(1);

    ans=double(up*ri)-ans;

    int an=int(ans+0.5);

    printf("%d\n",an);

    return 0;

}

---

2018.5.20