[BZOJ1941/Luogu2479][SDOI2010]Hide and Seek(KDT)

发布于 2018-05-11  154 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1941/Luogu2479][SDOI2010]Hide and Seek(KDT)

Description

小猪iPig在PKU刚上完了无聊的猪性代数课,天资聪慧的iPig被这门对他来说无比简单的课弄得非常寂寞,为了消除寂寞感,他决定和他的好朋友giPi(鸡皮)玩一个更加寂寞的游戏---捉迷藏。 但是,他们觉得,玩普通的捉迷藏没什么意思,还是不够寂寞,于是,他们决定玩寂寞无比的螃蟹版捉迷藏,顾名思义,就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后,他们决定iPig去捉giPi。由于他们都很熟悉PKU的地形了,所以giPi只会躲在PKU内n个隐秘地点,显然iPig也只会在那n个地点内找giPi。游戏一开始,他们选定一个地点,iPig保持不动,然后giPi用30秒的时间逃离现场(显然,giPi不会呆在原地)。然后iPig会随机地去找giPi,直到找到为止。由于iPig很懒,所以他到总是走最短的路径,而且,他选择起始点不是随便选的,他想找一个地点,使得该地点到最远的地点和最近的地点的距离差最小。iPig现在想知道这个距离差最小是多少。 由于iPig现在手上没有电脑,所以不能编程解决这个如此简单的问题,所以他马上打了个电话,要求你帮他解决这个问题。iPig告诉了你PKU的n个隐秘地点的坐标,请你编程求出iPig的问题。

Tag

KDT

解决思路

直接枚举每一个点,然后求与这个点最近的点和最远的点。这个可以用$$KDT$$求,注意要去掉自己。由于保证了题目中没有重复的点,所以在求最小距离的时候只要判断不是$$0$$即可。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1941/Luogu2479][SDOI2010]Hide and Seek(KDT)


HNCJ OIer