P4703 偷上网

    • 479通过
    • 4.4K提交
  • 题目提供者 Drench 管理员
  • 评测方式 云端评测
  • 标签 向量 枚举,暴力 计算几何 O2优化 Special Judge 高性能
  • 难度 普及+/提高
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Alice 和 Bob 生活在一个 $l \times l$ 的正方形房子里,由于 Bob 最近沉迷隔膜,Alice 决定要限制 Bob 上网的频率。

    Alice 建造了 $n$ 个无线信号屏蔽器,第 $i$ 个位于 $(x_i, y_i)$,屏蔽范围为 $\frac{l}{n}$。

    Bob 网瘾发作按捺不住上网的冲动,找到了你,帮他找到一个位置 $(x, y)$,使得没有被 Alice 的无线信号屏蔽器覆盖。

    输入输出格式

    输入格式:

    第一行两个整数 $n, l(1 \leq n \leq 10, 1 \leq l \leq 10^5)$,分别表示无线信号屏蔽器的个数和房子的大小。

    接下来 $n$ 行,每行 $2$ 个数,分别是 $x_i, y_i(0 \leq x_i, y_i \leq l)$,意义如上所述。

    输出格式:

    如果可以找到,输出两个数 $x, y(0 \leq x, y \leq l)$,意义如上所述,如果有多组解,输出任意一组即可。如果你输出的解满足到任意一个屏蔽器的距离都不小于 $\frac{l}{n} + 10^{-6}$,则视为正确。

    否则输出 "GG"。

    输入输出样例

    输入样例#1: 复制
    1 1
    0.000 0.000
    输出样例#1: 复制
    0.999 0.999
    输入样例#2: 复制
    1 2
    1.000 1.000
    输出样例#2: 复制
    GG
    输入样例#3: 复制
    2 2
    0.000 0.000
    2.000 2.000
    输出样例#3: 复制
    1.000 1.000
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。