Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
题目中已经说了choose a best direction to run,已经是沿着直线跑的意思In Reply To:雁过留声——计算几何,大胆猜想 Posted by:fanhqme at 2009-08-24 18:23:14 > 首先,要一个大胆的猜想: > 是否逃跑的最优路径一定可以是直线? > 这是对几何的一种直觉,一种瞬间闪烁的灵感。 > > 我的证明: > 只要证明如下命题原命题就可以得证: > 从一个点到另一个点,不可能因为一个炸弹的缘故走曲线。 > 把x,y,和时间轴作为三维,建立一个空间。 > 想象:一个炸弹爆炸的范围的形状 > 是个圆锥! > 自己的行动范围,即可以到达的点呢? > 如果没有炸弹,那么也是一个圆锥。 > 如果有一个炸弹... > 自己想象好了。如果想象清楚了,那么下面这个事情不难想清楚: > 设这个想象出来的图形是X > 用一个水平的面(时间相等)截X,上面任一点和自己原来的出发点(圆锥的顶点)连线中每一个点都在X内部。 > 这样,必然存在一个直线的逃跑路线! > > 得到这个结论,下面就比较简单了 > 设我们的特工最终跑到了基地边缘的A点。 > 若开始的起点是S,则对于每一个炸弹B,有 > BA>SA才可以 > 这样,我们可以在基地的圆周上选的点的范围,必然是在BS中垂线的与S相同的那侧。 > > 于是,算法流程:计算自己和每个炸弹连线的中垂线与圆周的交点,计算极角, > 然后计算区间的交,如果非空,输出Yes,否则No > > 我比较偷懒,用了一个替代的方法:在圆周上均匀的撒100000个点, > 依次判断是否BA>SA,最后输出。 > > 感谢数据,即使不小心把>=写成了>也让我AC了。 > Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator