AT_arc011_4.[ARC011D] きつねさんからの挑戦状

狐狸格雷正计划在城市里建造一个秘密的武器工厂。为了不让人类发现工厂的位置，他想把工厂建在这些人居住较少的偏僻地区。你是某国家派去阻止格雷活动的特工，并拿到了一张城市地图。城市由道路和住宅构成，这些都在地图上标示。地图可以看作一个二维平面，直线表示道路，坐标表示住宅。

现在，你收到另一名特工的情报，了解到了关于格雷选择工厂位置的标准：

1. 格雷认为工厂位置的难以发现度取决于工厂到最近道路和最近住宅的距离。
2. 假设武器工厂的坐标为 $ (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 $。
3. 格雷会选择那个使得评价函数 $ f(x, y) $ 最大的坐标 $ (x, y) $ 来建造工厂。
4. 工厂的坐标 $ (x, y) $ 要满足 $ -R \le x, y \le R $。
5. 这些坐标 $ (x, y) $ 是实数。

你需要根据这些信息和地图，找出格雷可能计划建造工厂的位置，并计算出评价函数 $ f(x, y) $ 的最大值。

输入格式

输入首先包括一行三个整数 $ N $、$ M $ 和 $ R $，用空格分隔。

• $ N $ 表示道路的数量，$ 1 \le N \le 16 $。
• $ M $ 表示住宅的数量，$ 1 \le M \le 16 $。
• $ R $ 表示工厂坐标 $ (x, y) $ 的限制条件，$ 1 \le R \le 1,000 $。

接下来有 $ N $ 行，每行三个整数 $ a_i $、$ b_i $、$ c_i $，代表第 $ i $ 条道路的方程 $ a_ix + b_iy + c_i = 0 $。

• 其中 $ a_i、b_i、c_i $ 的值为 $ -1,000 \le a_i, b_i, c_i \le 1,000 $。
• 不存在 $ a_i = 0 $ 且 $ b_i = 0 $ 的情况。

然后接下来有 $ M $ 行，每行两个整数 $ p_j $、$ q_j $，代表第 $ j $ 个住宅的坐标 $ (p_j, q_j) $。

• 对于 $ p_j、q_j $，有 $ -1,000 \le p_j, q_j \le 1,000 $。

注意：可能存在多个相同的直线或坐标。

输出格式

请输出在 $ -R \le x, y \le R $ 范围内，难以发现度评价函数 $ f(x, y) $ 的最大值。你的结果只要绝对或相对误差不大于 $ 10^{-6} $ 即可。请在输出末尾加换行。

数据范围与提示

• $ 1 \le N \le 16 $
• $ 1 \le M \le 16 $
• $ 1 \le R \le 1,000 $
• $ -1,000 \le a_i, b_i, c_i \le 1,000 $
• $ -1,000 \le p_j, q_j \le 1,000 $

本翻译由 AI 自动生成