CF394E.Lightbulb for Minister

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The Minister for education is coming! Naturally, nobody wants to perform poorly in front of such a honored guest. However, two hours before the arrival it turned out that one of the classes has a malfunctioning lightbulb — for some reason it doesn't get enough energy. The solution was found quickly: all we've got to do is to change the location of the lightbulb so that it got the maximum amount of energy.

Everybody knows that the power of the lightbulb equals , where C is some constant value and r__i is the Euclidean distance from the bulb to the i-th generator. Consequently, our task is to minimize . Of course, we know the positions of all generators.

The bulb should be on the ceiling of the class. The ceiling of the class is in the form of a strictly convex m-gon (the class itself has the form of a right prism with a strictly convex m-gon at the bottom). Help to find the optimum location for the bulb. Assume that all generators are in the plane of the class ceiling. Consider that the plane of the class ceiling has some Cartesian coordinate system introduced.

教育部长即将莅临!自然,谁都不希望在这样一位尊贵的来宾面前表现不佳。然而,在来宾抵达前两小时,人们发现某间教室的一盏灯泡出现了故障——不知何故,它无法获得足够的能量。解决方案很快便被找到:我们只需调整灯泡的位置,使其获得最大能量即可。

众所周知,灯泡的功率为
,
其中 CC 是某个常数,rir_i 表示灯泡到第 ii 个发电机的欧几里得距离。因此,我们的任务即为最小化
。
当然,所有发电机的位置均已知。

灯泡必须安装在教室天花板上。该教室天花板呈严格凸 mm 边形(教室本体则为一个底面是严格凸 mm 边形的直棱柱)。请帮助找出灯泡的最优安装位置。假设所有发电机均位于教室天花板所在平面内。设教室天花板所在平面已引入某个笛卡尔坐标系。

输入格式

The first line contains integer n (2 ≤ n ≤ 105) — the number of generators. Each of the next n lines contains a pair of integers x__i, y__i, representing the coordinates of the i-th generator in the plane of the class ceiling. It's guaranteed that no two generators have the same location.

The next line contains integer m (3 ≤ m ≤ 105) — the number of vertexes in the convex polygon that describes the ceiling of the class. Each of the following m lines contains a pair of integers p__i, q__i, representing the coordinates of the i-th point of the polygon in the clockwise order. It's guaranteed that the polygon is strictly convex.

The absolute value of all the coordinates don't exceed 106.

第一行包含一个整数 nn(2 ≤ n ≤ 1052 \leq n \leq 10^5)—— 发电机的数量。接下来的 nn 行中,每行包含一对整数 xix_i, yiy_i,表示第 ii 个发电机在教室天花板平面上的坐标。保证任意两个发电机的位置均不相同。

接下来一行包含一个整数 mm(3 ≤ m ≤ 1053 \leq m \leq 10^5)—— 描述教室天花板的凸多边形的顶点数。随后的 mm 行中,每行包含一对整数 pi, qip_i,\,q_i,表示按顺时针顺序给出的该多边形第 ii 个顶点的坐标。保证该多边形是严格凸的。

所有坐标的绝对值均不超过 10610^6。

输出格式

Print a single real number — the minimum value of the sum of squares of distances from the generators to the point of the lightbulb's optimal position. The answer will be considered valid if its absolute or relative error doesn't exceed 10 - 4.

输出一个实数——光源最优位置到各发电机的距离的平方和的最小值。若答案的绝对或相对误差不超过 10−410^{-4},则视为正确。

输入输出样例

  • 输入#1

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

    输出#1

    8.00000000

说明/提示

We'll define a strictly convex polygon as a convex polygon with the following property: no three vertices of the polygon lie on the same line.

我们将严格凸多边形定义为满足以下性质的凸多边形:该多边形中任意三个顶点都不共线。

输入解题思路,AI测评打分。不知道怎么写?

首页