P2479 [SDOI2010]hideseek

    • 45通过
    • 99提交
  • 题目提供者xcz12315
  • 标签 搜索 枚举,暴力 递归 各省省选 2010 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    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有且仅有一行:一个整数,为距离差的最小值。

    输入输出样例

    输入样例#1: 复制
    4
    0 0
    1 0
    0 1
    1 1
    
    输出样例#1: 复制
    1

    说明

    30%的数据中,2 <= N <= 1000;

    100%的数据中,2 <= N <= 100000,0 <= Xi, Yi <= 100000000。

    数据保证没有重点。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。