题解：CF1886B Fear of the Dark

· · 题解

看到图第一眼以为是分类讨论，一看题面，原来不是求最短路，而且坐标确定，距离相同，那就好做了。

思考一下什么情况下有一条合法路径：首先起点和终点都必须被灯光覆盖，其次覆盖起点和终点的灯光范围需要相交。

注意，覆盖起点和终点的灯可以是同一盏灯。

某盏灯覆盖起点或终点所需 w 为灯到它的距离，而使灯光范围接触所需 w 为两灯距离的一半。

设 \operatorname{dis}(x_a,y_a,x_b,y_b)=\sqrt{(x_a-x_b)^2+(y_a-y_b)^2} 表示 A(x_a,y_a)、B(x_b,y_b) 两点间距离，两盏灯坐标分别为 (lx_0,ly_0)、(lx_1,ly_1)。令灯 i 为覆盖起始点的灯，灯 j 为覆盖终点的灯，那么答案就为：

\min_{i \in \{0,1\},j \in \{0,1\}} \max \left\{ \begin{aligned} &\operatorname{dis}(0,0,lx_i,ly_i)\\ &\operatorname{dis}(px,py,lx_j,ly_j)\\ &\operatorname{dis}(lx_i,ly_i,lx_j,ly_j) \times \tfrac{1}{2} \end{aligned} \right.

AC 记录

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

inline double dis(double xa,double ya,double xb,double yb)
{
    return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}

int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        double px,py,lx[2],ly[2];
        scanf("%lf%lf%lf%lf%lf%lf",&px,&py,&lx[0],&ly[0],&lx[1],&ly[1]);
        double ans=1e18;
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
            {
                double w=max({
                    dis(0,0,lx[i],ly[i]),
                    dis(px,py,lx[j],ly[j]),
                    dis(lx[i],ly[i],lx[j],ly[j])/2.0
                });
                ans=min(ans,w);
            }
        printf("%.10lf\n",ans);
    }
    return 0;
}