Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:雁过留声——计算几何,大胆猜想

Posted by 323232 at 2009-09-11 20:31:04 on Problem 3747
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator