P3297 [SDOI2013]逃考

    • 92通过
    • 254提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 半平面相交,半平面交 计算几何 各省省选 2013 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    髙考又来了,对于不认真读书的来讲真不是个好消息为了小杨能在家里认真读书,他 的亲戚决定驻扎在他的家里监督他学习,有爷爷奶奶、外公外婆、大舅、大嫂、阿姨......

    小杨实在是忍无可忍了,这种生活跟监狱有什么区别!为了他亲爱的小红,为了他的 dota,他决定越狱!

    假设小杨的家是个n*m的矩阵,左下角坐标为(0, 0),右上角坐标为(xl, yl)。小 杨有n个亲戚,驻扎在矩阵里(位置不同,且不在矩阵的边上)。小杨家里的每个地方都被 亲戚监控着,而且只被距离最近的亲戚监控:

    也就是说假设小杨所在的位置是(3,3),亲戚A在(3,0), A距离小杨距离是3;亲戚 B在(6,7),则B距离小杨距离是5。距离A<距离B,所以(3,3)位置由A监控。

    如果“最近距离”出现同时有几个亲戚,那么那个位置同时被那几个亲戚监控。

    给出小杨的坐标(x0,y0)。因为被发现的人数越少,越狱成功的机会越大,所以小杨需 耍你设计一条越狱路线到达矩形的边上,且被发现的人数最少。

    Ps:小杨做的方向是任意的,也就是说路线上的任意位置H需耍是实数。

    保证一开始小杨只被一个亲戚监控着。

    输入输出格式

    输入格式:

    第一行 一个正整数t<=3表示数据个数

    接下来t个数据:

    第一行n表示亲戚个数

    第二行4个正整数表示举行右上角坐标(x1,y1)和小杨的坐标(x0,y0)

    接下来n行,每行2个正整数表示一个亲戚的位置

    输出格式:

    每个数据一个正整数表示越狱被发现人数的最小值

    输入输出样例

    输入样例#1: 复制
    2
    4
    10 10 5 5
    5 6
    3 5
    7 5
    5 3
    17
    14 12 7 6
    7 11
    6 9
    7 7
    1 10
    2 20
    1 6
    2 6
    1 1
    2 2
    5 1
    5 2
    13 1
    12 2
    12 7
    13 7
    12 11
    13 11
    输出样例#1: 复制
    1
    2

    说明

    数据解释:

    第一个数据, 小杨直接往上走,只被 (5,6) 监控过.

    第二个数据,小杨被 (7,7) 监控- 走到 (9,9) 被 (7,11) 监控, 然后直接往上走.

    数据规模:

    前 50%数据. n<=200;

    其余数据 n<=600.

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