← 返回题目列表

AtCoder · arc011_4

D. 来自狐狸先生的挑战

中文机器翻译题面 查看原题
2013.01.19 21:56 R 的范围已更改。

問題文

狐狸格雷正试图在城里建造一座秘密武器工厂。
他不想让人类知道他的工厂在哪里,所以他打算把工厂建在人烟稀少的偏远地区。
你是某个国家的特工,被派去阻止格雷的破坏活动,为了完成你的任务,你获得了一张该城市的地图。
城市由道路和住宅组成,所有这些都在地图上标记。
地图是 2 在维度平面中,道路被假定为直线,房屋被假定为坐标。

我刚刚从另一位代理商那里收到有关格雷将在哪里建造他的工厂的信息。
  1. 格雷正在思考見つかりにくさ取决于到武器工厂最近的道路的距离以及到最近的住宅的距离。
    • 武器工厂坐标 (x, y)
    • 兵工厂到最近道路的距离 dist_{road}(x, y)
    • 距离兵工厂最近的住所 当定义 dist_{point}(x, y)
    时, 表示見つかりにくさ的评估函数 f(x, y) 是 可以表示为 f(x, y) = dist_{road}(x, y) + dist_{point}(x, y)^2 。
  2. 灰色为评价函数 坐标使得 f(x, y) 是最大的 在 (x, y) 建造一座武器工厂。
  3. 武器工厂坐标 (x, y) 是一个整数 对于 R 反对 -R≦x,y≦R 符合。
  4. 座標 (x, y) 都是实数。

使用此信息和地图,您可以使用评估函数找出格雷计划在哪里建造武器工厂。 我决定找到 f(x, y) 的最大值。

入力

输入将以以下格式从标准输入给出。
N M R
a_{0} b_{0} c_{0}
:
a_{N-1} b_{N-1} c_{N-1}
p_0 q_0
:
p_{M-1} q_{M-1}
  1. 1 在线 3 整数 N M R 由半角空格分隔。
    • N 是道路数量, 1≦N≦16 符合。
    • M 是住宅数量, 1≦M≦16 符合。
    • R 是格雷正在建造的武器工厂的坐标。 在 (x, y) 的约束下, 来自行 1≦R≦1,000 符合。
  2. 2 从行 N+1 至行 N 线路是关于道路的 3 整数 a_i b_i c_i 由半角空格分隔。
    • i第条路是直的 给出为 a_ix + b_iy + c_i = 0 。 无法给出
    • a_i 为 -1,000≦a_i≦1,000 符合。
    • b_i 为 -1,000≦b_i≦1,000 符合。
    • c_i 为 -1,000≦c_i≦1,000 符合。
    • a_i = 0 和 b_i = 0 的情况。
  3. N+1 从行 N+1+M 至行 M 行与居住地相关 2 整数 p_j q_j 由半角空格分隔。
    • j第一个住处是坐标 (p_j, q_j) 。 无法给出
    • p_j 为 -1,000≦p_j≦1,000 符合。
    • q_j 为 -1,000≦q_j≦1,000 符合。
  4. 同一条直线可以多次给出,坐标也是如此。

出力

見つかりにくさ的评估函数 f(x, y) 的 已知 -R≦x,y≦R 中的最大值 1 按行输出。
输出至少有一个绝对误差或相对误差。 10^{−6} 或更少是可以接受的。
另外,在输出末尾放置一个换行符。

入力例 1

4 4 1
1 1 2
1 1 -2
1 -1 2
1 -1 -2
1 1
1 -1
-1 1
-1 -1

出力例 1

3.414213562373
图:输出示例 1 图示 当兵器工厂在
  • 座標 (0, 0) 建成时,评价函数的值为最大,值为 3.414213562373 。

入力例 2

7 5 3
-2 2 1
5 5 3
5 4 1
-2 2 -1
0 3 -4
-3 -1 -1
2 0 2
-2 4
-3 -3
4 3
4 -5
2 5

出力例 2

23.575923118987
  • 座標 (1.35714285714286, -1) 建成时,评价函数的值为最大,值为 23.575923118987 。