P3725 [AH2017/HNOI2017]队长快跑

· · 题解

本人与同学各种证明了两天，终于是把我们目前所知的问题全都证明出来了，如果你被网上各种只给做法不给证明的题解所困扰，希望这篇题解可以帮助到你。（拒绝感性理解和咕咕咕）

鸣谢 \_Cavalier23 与 Ninjia 的帮助。

个人认为先将做法看懂再去看证明会比较容易理解。

题解正文

明显，最优路径肯定是由一堆上凸和下凸路径拼起来的。那么我们就可以通过维护上凸和下凸来得到最优解。我们把射线分成两类，一类用来维护上凸路径，另一类用来维护下凸路径。（可以想象为上下两个方向，下面用 “上” 来表示维护上凸路径的一类， “下” 类似）分类标准是：在起点到终点的向量左边的射线如果与起点到终点的线段有交点，分入 “上” ，否则分入 “下” 。在起点到终点的向量右边的射线如果与起点到终点的线段有交点，分入 “下” ，否则分入 “上” 。接下来将 “上” 中的路径掰竖直向上，“下” 中的路径掰竖直向下（理由见下面的证明1）。

例子：

掰直前：

掰直后：

明显我们只需要走端点，然后我们考虑如何维护。

对于每一个点，我们可以记录下从起点到它的最优路径中它的上一个点是谁（如果有最优路径的话），这样我们就可以逐步还原最优路径。记点 i 的上一个点为 pre_i ，那么我们的问题就转换成如何求每个点的 pre 。然后发现这里有单调性：

对于一段上凸路径，考虑在末尾新加入一条射线。如果加入后并没有形成上凸包，就说明上一条射线没有切断上上个端点与当前端点的 联系，那么就可以直接删除最后的节点（样例如下）。这明显就可以用单调队列维护，维护好后队尾的端点就是新加入端点的 pre 。下凸路径相似。

但是不同指向的射线也有可能会相互影响，就如下图（以下的图都默认粉色的点是指上的，蓝色的点是指下的）：

对于 G ，我们可以发现 C 到 G 的路径被射线I 截断了，通过凸包的单调性，可以推得 有路径被截断时，起点到 G 的路径一定被第一条指下的射线截断。 此时到G点的最优路径应该是 S→E→I→G ，原先指上的端点一个都不经过。证明如下：

假如我们先走一段上凸路径，然后接上一段下凸到新加入的点（如下图）

那么在图中，我们连接 S,I，然后延长 ED,DC,BC 交 SI，得到下图：

在S→E 的下凸路径上的点一定都在三角形 SIE ，图中我们可以通过三角不等式得到

IE+IJ>JE=JD+DE JD+JK>KD=KC+CD KC+KL>LC=LB+BC SL+LB>SB

整合得

IA+AI+IE>IS+IE>SB+BC+CD+DE

其他情况类似，通过相似的做法也可以证明在不同指向的射线没有相互影响时，在上凸路径中的点的最优路径一定是从起点一直走上凸路径到它而非先先走一段下凸再走上来。如果感觉没听懂，可以看下面的例子：

图中 SC+CD+DE+EF<SB+BE+EF也可以用上面的方法证明。

回到正题，原来的上凸包被弹空了，我们维护的上凸包失效了，要想一个办法重新整出一个上凸包才行，这时我们发现到原先的"上凸包"与下凸包有一段是重合的，设它们从点 x 后分离，那么在 x 之前的点都不会与之后加入的点有直接连接（因为被射线 x 与 最后加入的射线挡住了）。那么我们可以直接把 x 作为新起点开始维护。这样上凸包又有了。

这里还有一个问题，就是射线的方向应该是通过判断它与新起点和终点的位置关系确定，不过其它题解都是直接在一开始就判断，这样没问题吗？答案是肯定的，详见下证明2。

证明1

不在起点与终点间的射线没有影响，它们不会经过起点到终点的线段（不然就无解了）。而被该射线分隔的射线（如下图中在C射线之上的）无法更新答案，因为它们的指向必须全部相同（不然就会有射线切到起点到终点的线段，造成无解情况），于是无法用来更新起点，而要更新起点一定会有更优的射线把它们全部弹掉。而它们也无法阻隔起点到终点，最后也肯定会被终点更新掉，所以不在起点与终点间的射线一定没有影响。

两条指向不同的射线，要么交点不在起点到终点之间，要么没有交点。不然绝对会将起点与终点分隔在两个区域。

两条指向相同的射线，证明就复杂一些了。

我们要关注的就是后面的射线是否会切断起点与前面的端点的连线，前面的射线是否会切断终点与后面的端点的连线，然后分类讨论。

1. 前不切，后不切

那就跟直接掰直没区别了。

2. 前不切，后切

举个例子： 通过一定的手玩，可以猜测后面的射线一定可以弹掉前面的射线。

证明：

以指上的射线为例，在前面的点称为 A ，后面的点称为 C 。

若射线 A 经过线段 ST ,那么就会造成无解情况(如下图)。

若射线 A 不经过线段 ST ,如果点 C 无法将 A 弹出，那么就必须在图中的阴影部分

而此时射线 C 要经过线段 SA ，必须同时经过线段 ST ，那么方向就不是朝上了，与条件冲突。

所以猜测是正确的,那么该情况和掰直达到的效果也就是一样的。

3. 前切，后不切

该情况的证明与情况2类似，不在此赘述。

4. 前切，后切

该情况下，两条射线都不经过线段 ST,因为若射线 A 经过 ST ,那么点 C 就必须在下图的阴影部分中，这样点 A 就被包含在三角形 STC 中，射线 A 也就只能经过该三角形的一条边，因此射线 A 不可能同时经过线 ST 和 CT 。

而两条射线都不经过线段 ST 的情况，这两条射线围成的部分（如下图中的蓝色部分）跟不在起点与终点间的射线围成的部分起到的作用是一样的。所以也可以直接掰直。

\

综上，所以情况都被证实可以了。

证明2

设旧起点为 S ,新起点为 S' ,终点为 T ，在 S'左边的射线不考虑；在三角形 STS'中的射线方向是不变的，枚举射线过的边就可以证明； 而在三角形外的射线如果要改变方向，那必须经过边 SS',不过这种情况明显非法。所以剩下的射线的方向全都不变。

总结

这个贪心做法虽然会考虑错许多情况，但这些情况都不会对答案造成影响（简直恶心），对出题人的脑洞五体投地。

代码：

#include<bits/stdc++.h>//码风奇丑，敬请见谅。 
using namespace std;
const int N=1e6+5;
int n,tx,ty,sx,sy,q[2][N],ql[2],qr[2],l,pre[N];
double ans;
struct P{
    int x,y;
    double w;
    bool operator < (const P&t)const{
        return x<t.x;
    }
    P operator - (const P&t)const{
        return (P){x-t.x,y-t.y,0};
    }
}a[N],b[N];
int dir(P a){//确定方向 
    double l=atan2(sy-a.y,sx-a.x),r=atan2(ty-a.y,tx-a.x);
    if(l<r)return l<a.w&&a.w<r;
    return a.w<r||a.w>l;
}
long long crs(P a,P b){//叉积判断位置， 
    return 1ll*a.x*b.y-1ll*b.x*a.y;
}
long long s2(int x){return 1ll*x*x;}
#define u1 b[q[ur][ql[ur]]]
#define u2 b[q[ur][ql[ur]+1]]
#define d1 b[q[dr][qr[dr]]]
#define d2 b[q[dr][qr[dr]-1]]
int main(){
    scanf("%d %d %d",&n,&tx,&ty);
    for(int i=1;i<=n;++i){
        scanf("%d %d %lf",&a[i].x,&a[i].y,&a[i].w);
    }
    sort(a+1,a+n+1);//将射线按x坐标排序 
    for(int i=1;i<=n;++i)if(a[i].x>0&&a[i].x<tx)b[++l]=a[i];//选出有用的射线 
    b[++l]=(P){tx,ty,0}; 
    for(int i=1;i<=l;++i){//两个队列队首元素永远都是起点
        int dr=dir(b[i]),ur=!dr,cg=dr? -1:1;
        if(ql[ur]<qr[ur]&&(crs(b[i]-u1,u2-u1)*cg)>=0){//判断路径是否被不同指向的射线截断 
            ql[dr]=qr[dr]+1;//将没用元素清空。
            ql[ur]++;
            while(ql[ur]<qr[ur]&&(crs(b[i]-u1,u2-u1)*cg)>=0)ql[ur]++;
            q[dr][++qr[dr]]=q[ur][ql[ur]];
            sx=u1.x;sy=u1.y;
        }else {
            while(ql[dr]<qr[dr]&&(crs(b[i]-d2,d1-d2)*cg)>=0)qr[dr]--;
        }
        pre[i]=q[dr][qr[dr]];
        q[dr][++qr[dr]]=i;
    }
    for(int i=l;i;i=pre[i])ans+=sqrt(s2(b[i].x-b[pre[i]].x)+s2(b[i].y-b[pre[i]].y)); 
    printf("%.10lf",ans);
    return 0;
}