hatate. Safest Points

hatate. Safest Points

ZOJ3376. 最安全点

downloadsource code (ZOJ3376.cpp) [几何(geometry), 宽度优先搜索(bfs)]

玩红白机的时候,很多游戏都有类似的安全点,并在小朋友间流传,很多BOSS战也体现了“找规律是王道啊”。不过现在的弹幕类游戏,要设计的弹幕都依靠安全点的话,那是很失败的,看高手的replay也会发现东方一些SC有安全点,不过这是高手刷graze用的,普通玩家还是正常下避比较简单。这题就定义了所谓的最安全点,当然复杂的弹幕曲线算不来,于是就出了最简单的激光。

  • 今どきの念写記者/姫海棠はたて(ひめかいどう はたて)
  • 伝統の幻想ブン屋/里に最も近い天狗/射命丸文(しゃめいまる あや)
  • 毘沙門天の弟子/寅丸星(とらまる しょう)

在一个w*h的格点区域内,有一些直线,定义一个点是危险点,如果它到某条直线的曼哈顿距离小于1;定义一个点是最安全点,如果它不是危险点,且到所有危险点的最小距离是最大的。如果所有点都是危险点,输出”MISS!”(STG中挂了一次称为1 miss),否则按字典序输出所有最安全点。

首先得把危险点求出来,一个点到一条之间的曼哈顿最近点要么是它水平射线的交点(当直线斜率绝对值大于1时),要么是它垂直射线的交点(当直线斜率绝对值小于1时),证明比较显然。然后对于1000条直线,每条直线都可以用O(1000)的复杂度求出其“附近”的危险点,方法有很多种,但O(1000^2)的方法应该是会TLE的。有了这些危险点后,从这些点出发做一次bfs,求出所有点到危险点的距离,复杂度为O(1000^2)。如果最大的距离等于0,那么”MISS!”,否则就输出所有距离最大的点。





©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/

Leave a Reply