P1378 油滴扩展 被搜索耽搁的贪心水题

· · 题解

题解居然全部是搜索。。。惊了

我来给大家开凿一下贪心的脑洞，显然贪心对于代码量的要求要小很多。

Step 1

为什么我们可以搜索？

因为N很小，可以枚举判断放与不放（废话）

如果N比现在大，我们就要考虑贪心了

以下是不够严谨的证明qwq：【你可以选择性跳过】

在平面内有两个点，不放设为A与B，要求以这两个点为圆心做圆，两圆半径之和为AB的长度。

显而易见，这两个圆相切（然并卵）

如果我们要求这两个圆的面积和最大呢？

新做的黑圆直径=2AB，故半径=AB，此时面积最大，为所求。

这个圆我们可以理解成A为圆心，AB为半径的圆，这时与上圆的面积相同。

所以我们可以得出一个结论：

有r1+r2=C时，令r1=C，r2=0此时面积最大。

如果运用函数的知识，我们令f(x)=pi*r*r，那么

存在 f(r1)+f(r2) < f(r1+r2)+f(0)

即 f(r1)+f(r2) < f(C)

令g(x)=f(x)+f(C-x)，可以推知 g(0.5C)最小， g(C)，g(0)最大，

g(x)在[0,0.5C]递增，[0.5C,C]递减。（证明略）

Step 2

接下来我们回归这道题，

如果你很反感我上面的数学balabala，你可以直接得知一个结论：

两个半径之和为定值的圆，其中较大的一个半径越大，总面积越大。

你可能会发现这只是一个常识可能不需要证明

推广到六个圆，两两比较同样成立。

之后我们就可以贪心了，每次在这个矩形内加入圆的时候，让所加入的圆的半径尽可能大。

然后呢？

结束了啊。

Step 3

其实是硬核凑三个步骤

讲一下代码实现qwq

先把矩形的上界下界全搞出来，每一个点和这四条边的距离，取最小值初始最大半径。

对半径排序，选择最大的那个加进去。

之后每次再加入的时候，和原有的所有圆进行比较，算出可行的最大的半径。（如果不行那就不放这个圆）

上代码看吧：

#include<bits/stdc++.h>
#include<queue>
#define pi 3.1415926//精度没必要那么高，毕竟你最后取整数
using namespace std;
int n,m;
int lx,ly,rx,ry;
struct node{
    int x,y;//位置
    double r;//半径
}a[10];
int min_(int a,int b,int c,int d){
    return min(min(a,b),min(c,d));
}
int cmp(node a,node b){
    return a.r>b.r;
}
double dis(node a,node b){
    int x=a.x,y=a.y;
    int xx=b.x,yy=b.y;
    return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
int main(){
    cin>>n;
    cin>>lx>>ly>>rx>>ry;//左边 上边 右边 下边
    if(lx>rx) swap(lx,rx);
    if(ly>ry) swap(ly,ry);//上下界处理一下
    int S=(rx-lx)*(ry-ly);//面积
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        a[i].r=min_(a[i].x-lx,rx-a[i].x,a[i].y-ly,ry-a[i].y);//到四条边距离的最小值
    }
    sort(a+1,a+n+1,cmp);//排序
    for(int i=1;i<=n;i++){
        for(int j=i-1;j>=1;j--){//每次加入的时候和之前已有的计算一遍
            if(a[j].r>0)
                a[i].r=min(a[i].r,dis(a[i],a[j])-a[j].r);
        }
    }
    double ans=0;
    for(int i=1;i<=n;i++){
        if(a[i].r>0){
            ans+=pi*a[i].r*a[i].r;
        }
    }
    cout<<S-(int)round(ans)<<endl;//注意四舍五入啊QAQ，round()函数要注意啊
    return 0;
}