题解：P16629 [GKS 2017 #E] Blackhole

· · 题解

题意简述

空间中有三个黑洞。需要放置恰好三个半径相同的球，使每个黑洞都被覆盖，且三个球的并集连通。求球半径的最小值。

解题思路

三个黑洞必定位于同一平面。把任意球心正交投影到这个平面，球心到黑洞的距离不会增大，球心之间的距离也不会增大。因此，覆盖关系与连通关系都不会被破坏。原问题可以转化为平面上的三个等半径圆。

先固定半径 r，判断是否存在合法方案。给每个黑洞指定一个覆盖它的圆，只需考虑两类分配方式。

第一类是三个圆各自负责一个黑洞。三个圆的相交图必须连通，而三个顶点的连通图中一定存在一个顶点与另外两个顶点连通。设这个中间圆负责 P_i，圆心为 O。

因为中间圆覆盖 P_i，所以有：

OP_i\le r

对于另一个黑洞 P_j，负责它的圆既要覆盖 P_j，又要与中间圆相交。这等价于：

OP_j\le r+2r=3r

必要性来自三角不等式。反过来，若 OP_j\le3r，就能在线段 OP_j 上放置一个圆心，使它到 P_j 的距离不超过 r，到 O 的距离不超过 2r。

因此，枚举中间圆负责的黑洞后，只需判断三个圆盘是否存在公共点：

\begin{aligned} OP_i & \le r \\ OP_j & \le3r \\ OP_k & \le3r \end{aligned}

第二类是某个圆负责至少两个黑洞。设它同时覆盖 P_j,P_k，圆心仍为 O。余下两个圆可以组成一条连接链，并由最后一个圆覆盖 P_i。

从 O 到 P_i，两次圆间连接最多贡献 4r。最后一次覆盖最多贡献 r，故条件为：

\begin{aligned} OP_i & \le5r \\ OP_j & \le r \\ OP_k & \le r \end{aligned}

这个条件也充分。沿线段 OP_i 依次放置另外两个圆心，即可同时满足相邻圆相交和末端覆盖。枚举单独的黑洞 P_i，同样得到三种情况。

至此，问题变为检查以下六组权值：

(1,3,3),(3,1,3),(3,3,1),(5,1,1),(1,5,1),(1,1,5)

对一组权值 (w_0,w_1,w_2)，需要判断以 P_i 为圆心、w_ir 为半径的三个圆盘是否有公共点。

三个圆盘若有公共点，则公共区域中一定存在某个圆心，或某两个圆的边界交点。否则，公共区域的边界没有由两段圆弧形成的顶点，只能等于某个完整圆盘。这个圆盘的圆心便属于另外两个圆盘，与假设矛盾。

圆心候选可直接用两点距离判断。对于边界交点，也无须显式建立整个平面坐标系。设检查第 i,j 个圆的交点，并记它们的半径为 R_i,R_j。以 P_i 为原点、P_iP_j 为横轴，交点坐标为 (x,\pm h)，其中：

\begin{aligned} x & =\frac{R_i^2-R_j^2+d_{ij}^2}{2d_{ij}} \\ h & =\sqrt{R_i^2-x^2} \end{aligned}

同一坐标系下，可把 P_k 写成 (y,z)，且令 z\ge0。由三边长度可得：

\begin{aligned} y & =\frac{d_{ik}^2-d_{jk}^2+d_{ij}^2}{2d_{ij}} \\ z & =\sqrt{d_{ik}^2-y^2} \end{aligned}

两个交点中，(x,h) 到 P_k 更近。只要满足：

\sqrt{(x-y)^2+(h-z)^2}\le R_k

就找到了三个圆盘的公共点。三个黑洞互不重合，因此公式中的 d_{ij} 不会为零。

可行性随 r 单调。对 [0,4000] 二分 100 次。每次检查枚举六组权值、三个圆心和三对圆，即可得到足够精确的答案。每组数据只进行固定次数的运算，时间复杂度和空间复杂度均为 O(1)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ld=long double;
const ld eps=1e-12;
ld d[3][3];
ld dis(const ld a[],const ld b[])
{
    ld res=0;
    for(int i=0;i<3;i++)res+=(a[i]-b[i])*(a[i]-b[i]);
    return sqrt(res);
}
bool fit(int u,const ld a[])
{
    for(int i=0;i<3;i++)if(d[u][i]>a[i]+eps)return 0;
    return 1;
}
bool cross(int i,int j,int k,const ld a[])
{
    ld len=d[i][j];
    if(len>a[i]+a[j]+eps||len<abs(a[i]-a[j])-eps)return 0;
    ld x,y,h,z;
    x=(a[i]*a[i]-a[j]*a[j]+len*len)/(2*len);
    y=(d[i][k]*d[i][k]-d[j][k]*d[j][k]+len*len)/(2*len);
    h=sqrt(max(0.0L,a[i]*a[i]-x*x));
    z=sqrt(max(0.0L,d[i][k]*d[i][k]-y*y));
    return hypot(x-y,h-z)<=a[k]+eps;
}
bool check(ld r,const int w[])
{
    ld a[3];
    for(int i=0;i<3;i++)a[i]=r*w[i];
    for(int i=0;i<3;i++)if(fit(i,a))return 1;
    for(int i=0;i<3;i++)for(int j=i+1;j<3;j++)if(cross(i,j,3-i-j,a))return 1;
    return 0;
}
bool check(ld r)
{
    const int w[6][3]={{1,3,3},{3,1,3},{3,3,1},{5,1,1},{1,5,1},{1,1,5}};
    for(int i=0;i<6;i++)if(check(r,w[i]))return 1;
    return 0;
}
ld solve()
{
    ld p[3][3];
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>p[i][j];
    for(int i=0;i<3;i++)for(int j=i+1;j<3;j++)d[i][j]=d[j][i]=dis(p[i],p[j]);
    ld l=0,r=4000;
    for(int i=0;i<100;i++)
    {
        ld mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    return r;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    cout<<fixed<<setprecision(10);
    int _=0;
    while(T--)cout<<"Case #"<<++_<<": "<<solve()<<'\n';
    return 0;
}