题解 P1378 【油滴扩展】

ylsoi · 2017-07-21 21:12:16 · 题解

这一道题目总体上来说还是蛮好做的，就是#深度优先搜索，然后根据前面所确定的油滴的坐标和半径来确定目前的油滴的半径，！！！但是有一个地方是需要注意的，就是如果这个油滴本身就在另外一个油滴的内部，那么我们就不能选择这个油滴，也就是当两个油滴之间的距离小于那个油滴的半径，我们就要把它变成0！！！！

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=10;
const double PI=3.1415926535;
bool s[maxn];
double x[maxn],y[maxn],r[maxn],xa,ya,xb,yb,ansmax;
int n;
double cal(int i)//这是计算当前的点的半径的函数
{
    double s1=min(abs(x[i]-xa),abs(x[i]-xb));
    double s2=min(abs(y[i]-ya),abs(y[i]-yb));
    double ans=min(s1,s2);
    for(int j=1;j<=n;j++)
    if(i!=j&&s[j])
    {
        double d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
        ans=min(ans,max(d-r[j],0.0));//如果距离都小于0了，那我还要你有何用
    }
    return ans;
}
void dfs(int k,double sum)
{
    if(k>n)
    {
        ansmax=max(ansmax,sum);
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!s[i])
        {
            r[i]=cal(i);
            s[i]=1;
            dfs(k+1,sum+r[i]*r[i]*PI);
            s[i]=0;
        }
    }
}
int main()
{
    double ss;
    scanf("%d",&n);
    scanf("%lf%lf%lf%lf",&xa,&ya,&xb,&yb);
    ss=abs(xa-xb)*abs(ya-yb); 
    for(int i=1;i<=n;i++)
    scanf("%lf%lf",&x[i],&y[i]);
    dfs(1,0);
    printf("%d",int(ss-ansmax+0.5));//四舍五入
    return 0;
}