题解：P16174 [ICPC 2014 NAIPC] Banjo
lailai0916
·
·
题解
题意简述
平面上有一个圆形岩浆池。从起点走到终点，每次连续经过岩浆的长度不能超过 t。求最短路程。
解题思路
把圆心平移到原点 O。记起点、终点为 A,B，OA=a，OB=b，两条射线的较小夹角为 \theta。
先判断线段 AB。若它不经过圆内，或圆内部分不超过 t，直接走线段最短。后文只考虑线段 AB 不合法的情况。
最短路径离开圆后可以直接拉直。因此，它由起点到圆周的线段、若干条圆内弦、圆周到终点的线段组成。每次到达圆周都会重置连续停留时间。
令：
\begin{aligned}
\alpha & =\arccos\frac{r}{a} \\
\beta & =\arccos\frac{r}{b}
\end{aligned}
当 $t>0$ 时，一条长度为 $t$ 的弦对应的圆心角为：
$$
\varphi=2\arcsin\frac{t}{2r}
$$
设需要跨过的圆心角为 $z$，并令 $k=\lfloor z/\varphi\rfloor$。弦长 $2r\sin(u/2)$ 关于 $u$ 是凹函数。固定总圆心角时，应尽量使用长度为 $t$ 的弦，仅保留一条不足 $t$ 的弦。因此圆内最短路程为：
$$
L(z)=kt+2r\sin\left(\frac{z-k\varphi}{2}\right)
$$
定义从圆外一点到偏转角为 $u$ 的圆周点的距离：
$$
g_c(u)=\sqrt{c^2+r^2-2cr\cos u}
$$
在 $0\le u\le\arccos(r/c)$ 内有：
$$
g_c''(u)=\frac{cr(c\cos u-r)(c-r\cos u)}{g_c(u)^3}\ge0
$$
需要最小化：
$$
F(x,y)=g_a(x)+g_b(y)+L(\theta-x-y)
$$
$L$ 在 $z=j\varphi$ 处不可导。先固定 $z=j\varphi$，并记 $s=\theta-j\varphi=x+y$。对应代价为：
$$
C(j)=jt+\min_x\left(g_a(x)+g_b(s-x)\right)
$$
$g_c$ 在可见圆弧上是凸函数，故括号内关于 $x$ 单峰，可以三分。其最小值关于 $s$ 仍为凸函数，所以 $C(j)$ 是凸数列。所有满足 $\theta-\alpha-\beta\le j\varphi\le\theta$ 的整数 $j$ 可以再用一次三分求最小值。
还需检查 $L$ 的光滑区间。固定其中完整弦的数量 $k$，将 $A$ 绕 $O$ 向 $B$ 旋转 $k\varphi$。前 $k$ 条弦的总代价固定为 $kt$。若光滑区间内存在最优解，剩余三段必须共线，因此其代价就是旋转后两点的直线距离。这样的候选仅可能落在 $k=\lfloor(\theta-\alpha-\beta)/\varphi\rfloor$ 对应的区间；代码再检查直线穿过圆内的弦长是否不超过 $t$。
若 $t=0$，只能沿圆周绕行。答案为两条切线与中间圆弧之和。
记 $K=\lceil\pi/\varphi\rceil$。每组数据的时间复杂度为 $O(\log K)$，空间复杂度为 $O(1)$；数值三分的轮数视为常数。
## 正确性证明
任取一条合法路径。两次重置之间的圆内部分可以替换为弦。圆外部分的最短路径由线段和圆周弧组成。若 $t>0$，其中的圆周弧可以替换为若干条合法弦；若 $t=0$，最短路径只能保留圆周弧。因此，最优路径必然属于解题思路中枚举的路径。
固定首尾圆周点与总圆心角。若两条未达到上限的弦对应角分别为 $u,v$，将其中一条增大、另一条等量减小。由于 $2r\sin(u/2)$ 是凹函数，总代价不会增加。反复调整后，至多剩一条不足 $t$ 的弦。这证明了 $L(z)$ 的公式。
在 $L$ 的光滑区间内，分别对 $x,y$ 求导。极值条件要求起点线段、剩余弦和终点线段到圆心的垂直距离相等。它们按同一方向连接圆周，故三条线段共线。旋转前 $k$ 条完整弦后，代码检查的直线路径包含所有光滑区间内的候选。
其余极小值只能位于 $z=j\varphi$。此时 $x+y$ 已固定。函数 $g_a(x)+g_b(s-x)$ 是凸函数，三分能求出该 $j$ 的最小代价。对 $x$ 取最小值后，结果仍关于 $s$ 凸。因此 $C(j)$ 是凸数列，整数三分不会遗漏最优的 $j$。
算法比较直线路径、所有不可导点的最优路径与唯一可能的光滑区间候选。它覆盖了每条最优路径，因此输出全局最短路程。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const ld eps=1e-12;
ld a,b,r,t,d,ga,gb,al;
ld dis(ld x,ld y)
{
return sqrtl(x*x+r*r-2*x*r*cosl(y));
}
ld outer(ld x)
{
ld l=max(0.0L,x-gb),rr=min(ga,x);
for(int i=1;i<=80;i++)
{
ld m1=(2*l+rr)/3,m2=(l+2*rr)/3;
if(dis(a,m1)+dis(b,x-m1)<dis(a,m2)+dis(b,x-m2))rr=m2;
else l=m1;
}
return dis(a,(l+rr)/2)+dis(b,x-(l+rr)/2);
}
ld cost(ll k)
{
return (ld)k*t+outer(d-(ld)k*al);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x1,y1,x2,y2,xc,yc,ri,ti;
while(cin>>x1>>y1>>x2>>y2>>xc>>yc>>ri>>ti&&ri)
{
x1-=xc;y1-=yc;x2-=xc;y2-=yc;
r=ri;t=ti;
a=hypotl(x1,y1);b=hypotl(x2,y2);
ld dx=x2-x1,dy=y2-y1;
ld s=-(x1*dx+y1*dy)/(dx*dx+dy*dy);
s=max(0.0L,min(1.0L,s));
ld h=hypotl(x1+s*dx,y1+s*dy);
ld ans=hypotl(dx,dy);
if(h<r-eps&&2*sqrtl(r*r-h*h)>t+eps)
{
d=acosl(max(-1.0L,min(1.0L,(x1*x2+y1*y2)/(a*b))));
ga=acosl(r/a);gb=acosl(r/b);
if(t==0)ans=dis(a,ga)+dis(b,gb)+r*(d-ga-gb);
else
{
al=2*asinl(t/(2*r));
ld dm=d-ga-gb;
ll lo=(ll)ceill((dm-eps)/al),hi=(ll)floorl((d+eps)/al);
ll l=lo,rr=hi;
while(rr-l>8)
{
ll m1=l+(rr-l)/3,m2=rr-(rr-l)/3;
if(cost(m1)<cost(m2))rr=m2-1;
else l=m1+1;
}
ans=1e100L;
for(ll i=l;i<=rr;i++)ans=min(ans,cost(i));
ll k=max(0LL,(ll)floorl((dm+eps)/al));
ld x=d-(ld)k*al;
ld len=sqrtl(a*a+b*b-2*a*b*cosl(x));
ld hh=a*b*sinl(x)/len;
if(hh<=r+eps&&2*sqrtl(max(0.0L,r*r-hh*hh))<=t+eps)ans=min(ans,(ld)k*t+len);
}
}
cout<<fixed<<setprecision(2)<<ans<<'\n';
}
return 0;
}
```