一个有趣的算法题：别惊动魔王？
题目如下：
琼斯博士在寻宝的过程中，来到了一个平面图呈矩形的封闭房间。
矩形的宽度为w，高度为h。为方便描述，我们将矩形左上角坐标定为(0, 0)，右下角坐标定为(w, h)。
房间的入口在矩形上沿的中点(即(w/2, 0))，出口在矩形下沿的中点(即(w/2, h))。狡猾的魔王还放置了许多红外探测器，一旦进入探测器的探测半径以内，将触发警报。
现在琼斯博士向您求助，他能否全身而退不惊动魔王？
输入：boolean escape(int w, int h, int n, double[] x, double[] y, double[] r)
w为矩形宽度，h为矩形高度，n为探测器总数。第i个探测器的坐标为(x[i],y[i])，探测半径为r[i]。
输出：true or false
石更不起来君
10 years, 7 months ago
Answers
不求最短，只求能走的话，把探测器的边缘当作墙，左手扶墙走，如果走回入口说明是封闭的无法脱出，如果走到出口那就可以走出去
先求所有的直线／圆之间的交点，分别记录下来（四个顶点和入口出口也都记录为交点），然后从入口向左的直线开始找最近的交点，碰到交点就把“当前在走的线”更换，然后循环继续找交点，直到找到入口“交点”返回false，出口“交点”返回true
“最近的交点”的搜索方向，如果当前在走的线是直线（边），那么就是朝内部（上边沿的下面，etc），如果是圆弧，那么就是朝远离圆心的方向
求搜索方向，确定方向后找下一个节点等操作都是o1的，求所有交点虽然是平方级，但是是探测器数量的平方，感觉上应该还比较快
好地地唔得嘅
answered 10 years, 7 months ago
