先考虑逆时针给出的多边形。对于不完全位于 上的每条有向边 ，可行的微小平移向量 必须满足 。负值会导致该边附近与墙产生正面积的重叠，等号表示允许的滑动。完全位于 上的边不施加此限制。
这些条件与朝向墙外的条件也足以保证一直沿 移动即可移出。用平行于 的直线截取多边形：墙内部的边界不允许沿 从多边形内部穿出，因此每个非空内部截面都是一直延伸至开口的区间。将其朝外平移不会碰到墙。经过顶点的截面可用极限处理。
对于任意连续的成功路径，取足够小的非零位移，同样必须满足上述所有不等式。位于开口上的边方向相同，而所有边向量之和为 ，所以可行的非零位移只能朝向墙外。如果它平行于开口，则必须与所有边平行，与多边形面积为正矛盾。因此改变方向不会增加可行性。
可行方向区间的边界平行于某条边。枚举每条边的两个方向，并检查所有条件，可得 的算法。所附 naive 程序实现此算法，可通过完整限制。
还可以在线性时间内求解。令 ，逆时针时 ，顺时针时 ，并定义 。忽略正比例缩放，朝外的向量可写为 。每条相关边给出
系数为正时更新下界，为负时更新上界；系数为零且右侧为正时无解。最终下界不大于上界时有解，必须允许等号。
用分子和正分母保存分数，交叉相乘比较即可，无需浮点数。时间复杂度为 ，存储输入的空间复杂度为 。内积、外积的绝对值不超过 ，比较分数时每个乘积的绝对值不超过 ，有符号 位整数足够。
子任务 1 只有三角形，将开口对面的顶点朝开口内部一点移动即可，答案恒为可行。计入读取输入的时间为 。
Solution written by GPT
