P16191 [COI 2018] Svjetlost Light

3 s, 1024 MB.

On the plane, suppose we have a convex polygon $P$, and we place a light source $T$ outside the polygon. Then it will illuminate some edges of the polygon: if $A$ and $B$ are two adjacent vertices of the polygon, then the edge $AB$ is illuminated if and only if the area of triangle $TAB$ is non-zero, and this edge does not intersect the interior of the polygon. The brightness of the polygon is defined as the sum of the lengths of the illuminated edges, and the maximum brightness of the polygon means the maximum brightness we can obtain by choosing the best position of the light source $T$. The distance from point $T$ to the polygon can be arbitrary, and the coordinates of $T$ do not have to be integers.  Figure 4: The polygons $P, P_1, P_2$ and $P_3$ in the second sample, with the optimal brightness marked. Given a convex polygon $P$ with vertices in order $A_1, A_2, \ldots, A_n$. The polygon changes over $q$ operations: in the $j$-th operation, we delete one existing vertex to obtain a new polygon $P_j$. More precisely, the vertices of polygon $P_j$ are the vertices of $P$ that have not been deleted yet, and their order is the same as in the original polygon $P$. It can be seen that each polygon $P_j$ is still convex. Please compute the maximum brightness of the initial polygon $P$ and of each resulting polygon $P_1, P_2, \ldots, P_q$.

The first line contains a positive integer $n$, the number of vertices of the initial polygon $P$. The next $n$ lines each contain two integers $x_j$ and $y_j\ (-10^9\le x_j, y_j \le 10^9)$, the coordinates of vertex $A_j$. Then a line contains an integer $q\ (0 \le q \le n - 3)$, the number of changes. The next $q$ lines each contain an integer $k_j\ (1 \le k_j \le n)$, meaning that in the $j$-th operation we delete vertex $A_{k_j}$. It is guaranteed that the vertices of polygon $P$ are given in counterclockwise order, there are no consecutive parallel edges, and all deletion indices $k_j$ are pairwise distinct.

Output $q + 1$ lines. The first line outputs the maximum brightness of the initial polygon $P$. For line $j\ (1 \le j \le q)$, output the maximum brightness of polygon $P_j$ after the $j$-th change. The absolute or relative error is allowed to be at most $10^{−5}$ compared to the standard answer.

### Subtasks ::cute-table{three} |ID|Score|Constraints| |:-:|:--:|:--------:| |$1$|$12$|$n\le 100$| |$2$|$14$|$n\le 2000$| |$3$|$14$|$n\le 100\,000,q=0$| |$4$|$29$|$n\le 100\,000$, and for all $j = 1,\ldots, q − 1$ we have $k_j < k_{j+1}$| |$5$|$31$|$n\le 100\,000$| Translation source: GPT 4.1 mini. Translated by ChatGPT 5