luogu#P4703. 偷上网

    ID: 8729 远端评测题 2000ms 500MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>计算几何Special JudgeO2优化枚举暴力向量洛谷月赛

偷上网

题目描述

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

Alice 建造了 nn 个无线信号屏蔽器,第 ii 个位于 (xi,yi)(x_i, y_i),屏蔽范围为 ln\frac{l}{n}

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

输入格式

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

接下来 nn 行,每行 22 个数,分别是 xi,yi(0xi,yil)x_i, y_i(0 \leq x_i, y_i \leq l),意义如上所述。

输出格式

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

否则输出 "GG"。

1 1
0.000 0.000
0.999 0.999
1 2
1.000 1.000
GG
2 2
0.000 0.000
2.000 2.000
1.000 1.000