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 自动生成**

无

无