← 返回题目列表

Codeforces · 394/E

E. 部长的灯泡

中文机器翻译题面 查看原题

教育部长来了!当然,没有人愿意在这样的贵客面前表现不佳。然而,在抵达前两小时,发现其中一班的灯泡出现故障——由于某种原因,它没有获得足够的能量。解决方案很快就找到了:我们所要做的就是改变灯泡的位置,使其获得最大的能量。

每个人都知道灯泡的功率等于 $$\frac{C}{\sum_{i=1}^{n} r_i^2}$$,其中 C 是某个常数值,ri 是从灯泡到第 i 个发电机的欧几里德距离。因此,我们的任务是最小化 $$\sum_{i=1}^{n} r_i^2$$。当然,我们知道所有发电机的位置。

灯泡应位于班级的天花板上。类的上限是严格凸 m 边形的形式(类本身具有直棱柱的形式,底部有严格凸 m 边形)。帮助找到灯泡的最佳位置。假设所有生成器都位于类天花板的平面内。考虑到类天花板的平面引入了一些笛卡尔坐标系。

输入

第一行包含整数 n (2 ≤ n ≤ 105) — 生成器的数量。接下来的 n 行中的每一行都包含一对整数 xi、yi,表示第 i 个生成器在类上限平面中的坐标。保证没有两个发电机具有相同的位置。

下一行包含整数 m (3 ≤ m ≤ 105) — 描述类上限的凸多边形中的顶点数。接下来的m行中的每一行都包含一对整数pi,qi,表示按顺时针顺序排列的多边形第i个点的坐标。保证多边形是严格凸的。

所有坐标的绝对值不超过106。

输出

打印一个实数 - 从发电机到灯泡最佳位置点的距离平方和的最小值。如果答案的绝对误差或相对误差不超过 10 - 4,则答案将被视为有效。

示例

输入 #1

4
3 2
3 4
5 4
5 2
4
3 3
4 4
5 3
4 2

输出 #1

8.00000000

注意

我们将严格凸多边形定义为具有以下属性的凸多边形:多边形的三个顶点不位于同一条线上。