P12623 [ICPC 2025 NAC] Geometry Rush

你正在玩今夏最热门的节奏动作平台游戏——Geometry Rush！游戏在一个二维平面上进行。你的角色从 $(0,0)$ 出发，每秒必须以 $45$ 度角向上或向下移动，即从位置 $(x,y)$ 移动到 $(x+1,y+1)$ 或 $(x+1,y-1)$。你可以在每秒改变移动方向，但不能在移动过程中调整。游戏中有从天花板和地面突出的障碍物需要躲避。若在 $w$ 秒后到达终点线 $x=w$ 且未触碰任何障碍物，则获胜。 游戏区域的垂直范围为 $y=-h$ 到 $y=h$。障碍物由两条多边形曲线组成：一条从 $(0,h)$ 延伸到 $(w,h)$ 表示变化高度的天花板，其顶点的 $x$ 坐标非递减，$y$ 坐标在 $[-h,h]$ 范围内；另一条从 $(0,-h)$ 延伸到 $(w,-h)$ 表示地面，其顶点满足类似约束。 你的角色被视为一个无限小的点：从 $(x,y)$ 移动到 $(x+1,y \pm 1)$ 时，若移动路径与任一障碍物相交（包括恰好接触多边形曲线）则游戏失败。 为了增加挑战性，你开始设定特殊目标：无论从终点线 $x=w$ 的哪个位置穿过均可获胜，但求能穿过的最大 $y$ 值和最小 $y$ 值分别是多少？

第一行包含四个整数 $n$、$m$、$w$ 和 $h$（$3 \leq n, m \leq 10^{5}$；$3 \leq w, h \leq 10^{5}$），分别表示天花板和地面多边形曲线的顶点数，以及游戏区域的宽度和高度。 接下来 $n$ 行每行两个整数 $x$ 和 $y$（$0 \leq x \leq w$，$-h \leq y \leq h$），按从左到右顺序给出天花板曲线的顶点坐标。保证第一个顶点为 $(0,h)$，最后一个为 $(w,h)$。 随后 $m$ 行以相同格式给出地面曲线的顶点坐标，首尾顶点分别为 $(0,-h)$ 和 $(w,-h)$。 对于两条曲线：$x$ 坐标非递减，顶点互不重复，曲线不自交。两条曲线均不经过 $(0,0)$（若曲线相交则游戏无法获胜）。

若游戏无法获胜，输出 $\texttt{impossible}$。否则输出两个整数：可到达终点线 $x=w$ 的最小和最大 $y$ 值。

翻译由 DeepSeek V3 完成