TOAD 12 - Level with me

Problem

Alan 和 Danny 在一座山的两边。初始时两人均在海平面上。他们想在山上的某个位置碰面，并且任意时刻两人所在地的海拔高度都相同。这是否总是可行的？

山就是一条折线段，保证一个 \(x\) 只对应一个 \(y\) ，山上每个点均在海平面上，且山两段海拔为 0 。

Solution

首先我们可以给山的每个顶点的坐标离散化掉，因为山只有形状才是有用的。于是我们把山上任意一个整数高度的点依次编号，容易知道点的个数一定是有限的。

考虑任意一个二元组 \((a, b) (a \neq b)\) 表示 Alan 在点 \(a\) 而 Danny 在点 \(b\) 。考虑构一个二元组的图，两个二元组之间有边当且仅当一个二元组经过一步之后可以到达另一个二元组。注意两个特殊的二元组：两人同在海平面以及两人同在最高点。这两个二元组的度数大小只有一。对于一个连通块来说，所有点的度数和为偶数，所以这两个二元组一定在同一个连通块中，也就是这两个二元组是连通的，所以两人相遇总是可行的。