P1378 油滴扩展

斯德哥尔摩 · 2018-10-21 22:32:12 · 个人记录

P1378 油滴扩展

比较有思维深度的DFS。

要不然怎么能说是DFS,\text{深度优先搜索}呢。。。

先深搜，然后根据前面所确定的油滴的坐标和半径来确定目前的油滴的半径。

但是有一个地方是需要注意：

如果这个油滴本身就在另外一个油滴的内部，那么我们就不能选择这个油滴！

也就是当两个油滴之间的距离小于那个油滴的半径，我们就要把它变成0。

输出的答案为剩余的面积，还要四舍五入。。。

可以这么做：

先搜索求出最大覆盖面积，然后将答案+=0.5，最后用矩形总面积减去答案即可。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 10
using namespace std;
int n;
double Area,ans=0;
double r[MAXN];
bool used[MAXN];
struct Point{
    double x,y;
    friend double dis(const Point &p,const Point &q){
        return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
    }
}s,t,point[MAXN];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
double calculate(int i){
    double s1=min(fabs(point[i].x-s.x),fabs(point[i].x-t.x)),s2=min(fabs(point[i].y-s.y),fabs(point[i].y-t.y));
    double s=min(s1,s2);
    for(int j=1;j<=n;j++)if(i!=j&&used[j])s=min(s,max(dis(point[i],point[j])-r[j],0.0));
    return s;
}
void dfs(int x,double sum){
    if(x>n){
        ans=max(ans,sum);
        return;
    }
    for(int i=1;i<=n;i++)
    if(!used[i]){
        r[i]=calculate(i);
        used[i]=true;
        dfs(x+1,sum+r[i]*r[i]*M_PI);
        used[i]=false;
    }
}
void work(){
    dfs(1,0);
    printf("%d\n",(int)(Area-ans+0.5));
}
void init(){
    n=read();
    s.x=read();s.y=read();t.x=read();t.y=read();
    Area=fabs(s.x-t.x)*fabs(s.y-t.y);
    for(int i=1;i<=n;i++){point[i].x=read();point[i].y=read();}
}
int main(){
    init();
    work();
    return 0;
}