P1378 油滴扩展
斯德哥尔摩
2018-10-21 22:32:12
[P1378 油滴扩展](https://www.luogu.org/problemnew/show/P1378)
比较有思维深度的$DFS$。
要不然怎么能说是$DFS,\text{深度优先搜索}$呢。。。
先深搜，然后根据前面所确定的油滴的坐标和半径来确定目前的油滴的半径。
但是有一个地方是需要注意：
如果这个油滴本身就在另外一个油滴的内部，那么我们就不能选择这个油滴！
也就是当两个油滴之间的距离小于那个油滴的半径，我们就要把它变成$0$。
输出的答案为剩余的面积，还要四舍五入。。。
可以这么做：
先搜索求出最大覆盖面积，然后将答案$+=0.5$，最后用矩形总面积减去答案即可。
附代码：
```cpp
#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;
}
```