问题描述

狐狸格雷打算在城市中心建立一个秘密武器工厂。
为了不让人类知道工厂的位置，他计划在人类居住较少的偏远地区建立工厂。
你是某国派往阻止格雷行动的特工，为了完成任务，某国提供了城市地图给你。
城市由道路和住宅组成，它们都标示在地图上。
地图是二维平面，道路表示为直线，住宅表示为坐标。

现在你收到了其他特工提供的有关格雷建立工厂位置的情报：

1. 格雷所考虑的难以发现程度取决于距离最近的道路和距离最近的住宅之间的距离。
2. 定义以下变量：
   • 工厂坐标为 $(x, y)$；
   • 距离工厂最近的道路距离为 $dist_{road}(x, y)$；
   • 距离工厂最近的住宅距离为 $dist_{point}(x, y)$；
3. 难以发现程度评估函数 $f(x, y)$ 可以表示为 $f(x, y) = dist_{road}(x, y) + dist_{point}(x, y)^2$。
4. 格雷将在使评估函数 $f(x, y)$ 的值最大的坐标 $(x, y)$ 处建立工厂。
5. 工厂坐标 $(x, y)$ 满足 $-R≦x,y≦R$，其中 $R$ 是一个整数。
6. 坐标 $(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. 第一行包含三个整数 $N$ $M$ $R$，以空格分隔。

• $N$ 是道路的数量，满足 $1≦N≦16$。
• $M$ 是住宅的数量，满足 $1≦M≦16$。
• $R$ 是格雷建设工厂坐标 $(x, y)$ 的约束条件，满足 $1≦R≦1,000$。

3. 第二行到第 $N+1$ 行分别给出了 $N$ 条道路的三个整数 $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$ 的情况。

5. 第 $N+1$ 行到第 $N+M+1$ 行分别给出了 $M$ 个住宅的两个整数 $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$。

7. 可能会有多条相同的直线和坐标。

输出

输出评估函数 $f(x, y)$ 在 $-R≦x,y≦R$ 范围内的最大值，以一行输出。
如果输出的绝对误差或相对误差至少有一个小于 $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$。