Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:1024 MB

#1947. Svjetlost

统计

题面翻译

在平面上,如果我们有一个凸多边形 P,我们将光源放置在位于外部的点 T 多边形,它照亮了 P 的一些边——如果 A 和 B 是两个连续的多边形顶点,那么 如果三角形 4 T AB 的面积不为零,并且它不与 多边形。 多边形的亮度是亮边长度之和,最大 多边形的亮度是如果我们选择一个最佳点 T,我们可以达到的最大可能亮度。 点T到多边形的距离可以是任意的,点T的坐标不可以 必须是整数。

16.png

图 4:来自第二个测试用例的多边形 P、P1、P2 和 P3,标记了最佳亮度。

给定一个凸多边形 P,其顶点分别为点 A1、A2、... 。 多边形是 在 q 步中改变——在第 j 步中,我们删除一个现有的多边形顶点,并获得一个新的多边形 Pj。 更准确地说,多边形 Pj 的顶点是 P 中尚未被删除的顶点,它们的 顺序与多边形 P 中的相同。很容易看出每个多边形 Pj 也是凸的。

确定多边形 P 和每个获得的多边形的最大亮度P1、P2、... . . , Pq。

题目描述

In a plane, if we have a convex polygon P, and we place a source of light at a point T located outside the polygon, it lights up some edges of P — if A and B are two consecutive polygon vertices, then the edge AB is lit up if the area of the triangle 4 T AB is not zero, and if it doesn’t intersect the inside of the polygon. The brightness of the polygon is the sum of the lengths of lit up edges, and the maximal brightness of a polygon is the maximal possible brightness we can achieve if we select an optimal point T. The distance between point T and the polygon can be arbitrary, and the coordinates of point T don’t necessarily need to be integers.

16.png

Figure 4: Polygons P, P1, P2 and P3 from the second test case, the optimal brightness is marked.

You are given a convex polygon P whose vertices are, respectively, points A1, A2, . . . , An. The polygon is changed in q steps — in the jth step, we delete an existing polygon vertex, and obtain a new polygon Pj . More precisely, the vertices of polygon Pj are the vertices of P that haven’t been deleted yet, and their order is the same as in polygon P. It is easy to see that each polygon Pj is convex too.

Determine the maximal brightness of the polygon P and each of the obtained polygons P1, P2, . . . , Pq.

Input

The first line of input contains the positive integer n — the number of vertices of the initial polygon P. The jth of the following n lines contains two integers xj and yj $(−10^9 ≤ x_j , y_j ≤ 10^9 )$ — the coordinates of vertex Aj . The following line contains the integer q (0 ≤ q ≤ n − 3) — the number of steps. The jth of the following q lines contains the integer kj (1 ≤ kj ≤ n) that denotes that in the jth step we delete the vertex $A_{k_j}$ . You can assume that the vertices Aj in polygon P are given counter-clockwise, that two consecutive parallel lines do not exist, and that all indices kj are mutually distinct.

输入的第一行包含正整数 n——初始多边形 P 的顶点数。 以下 n 行的第 j 行包含两个整数 xj 和 yj $(−10^9 ≤ x_j , y_j ≤ 10^9 )$ — 坐标 顶点 Aj 。

以下行包含整数 q (0 ≤ q ≤ n − 3) — 步数。 第 j 个 以下 q 行中包含整数 kj (1 ≤ kj ≤ n),表示在第 j 步中我们删除 顶点 $A_{k_j}$ . 您可以假设多边形 P 中的顶点 Aj 是逆时针给出的,即两个 不存在连续的平行线,并且所有索引 kj 是相互不同的。

Output

You must output q + 1 lines. The first line must contain the maximal brightness of the initial polygon P, and the jth of the following q lines must contain the maximal brightness of polygon Pj obtained after j steps. For each line of output, an absolute and relative deviation from the official solution by $10^{−5}$ will be tolerated.

您必须输出 q + 1 行。 第一行必须包含初始多边形 P 的最大亮度, 并且以下q行的第j行必须包含在j之后获得的多边形Pj的最大亮度 脚步。

对于每一行输出,与官方解的绝对和相对偏差 $10^{−5}$ 将是 容忍。

样例 #1

样例输入 #1

4
0 0
10 0
10 10
0 10
12

样例输出 #1

20.000000
24.142136

样例 #2

样例输入 #2

6
2 2
4 0
6 0
8 2
8 4
2 4
3143

样例输出 #2

10.828427
11.300563
10.944272
11.656854

Scoring

17.png