#PQJ152x4168. QOJ 152_4168

    ID: 2630 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2010

QOJ 152_4168

Hide and Seek (hideseek) 题目描述 iPig 在大肥猪学校刚上完了无聊的猪文课,天资聪慧的iPig 被这门对他来说无比简单的 课弄得非常寂寞,为了消除寂寞感,他决定和他的好朋友giPi(鸡皮)玩一个更加寂寞的游 戏——捉迷藏。 但是,他们觉得,玩普通的捉迷藏没什么意思,还是不够寂寞,于是,他们决定玩寂寞 无比的螃蟹版捉迷藏,顾名思义,就是说他们在玩游戏的时候只能沿水平或垂直方向走。一 番寂寞的剪刀石头布后,他们决定iPig 去捉giPi。由于他们都很熟悉大肥猪学校的地形了, 所以giPi 只会躲在大肥猪学校内N 个隐秘地点,显然iPig 也只会在那N 个地点内找giPi。 游戏一开始,他们从这N 个隐秘地点之中选定一个地点,iPig 保持不动,然后giPi 用30 秒 的时间逃离现场(显然,giPi 不会呆在原地)。然后iPig 会随机地去找giPi,直到找到为止。 由于iPig 很懒,所以他到总是走最短的路径,而且,他选择起始点不是随便选的,他想找 一个地点,使得该地点到(除了这个地点以外的)最远的地点和最近的地点的距离差最小。 iPig 现在想知道这个距离差最小是多少。 由于iPig 现在手上没有电脑,所以不能编程解决这个如此简单的问题,所以他马上打 了个电话,要求你帮他解决这个问题。iPig 告诉了你大肥猪学校的N 个隐秘地点的坐标,请 你编程求出iPig 的问题。 输入格式 输入文件hideseek.in: 第1 行:一个整数N; 第2 ~ (N + 1)行:每行两个整数Xi,Yi,表示第i 个地点的坐标。 输出格式 输出文件hideseek.out 有且仅有一行:一个整数,为距离差的最小值。 样例输入 4 0 0 1 0 0 1 1 1

样例输出 1 数据规模 30%的数据中,2 <= N <= 1000; 100%的数据中,2 <= N <= 100000,0 <= Xi, Yi <= 100000000。 数据保证没有重点。