P16191 [COI 2018] Svjetlost 光

3s，1024MB。

在平面上，若我们有一个凸多边形 $P$，并且在多边形外放置一个光源 $T$，那么它会照亮多边形的一些边——如果 $A$ 和 $B$ 是多边形的两个相邻顶点，则边 $AB$ 会被照亮，当且仅当三角形 $TAB$ 的面积不为零，且该边不与多边形内部相交。多边形的亮度定义为被照亮边的长度之和，而多边形的最大亮度是指我们选择最优光源位置 $T$ 所能得到的最大亮度。点 $T$ 与多边形的距离可以任意，$T$ 的坐标不必为整数。  图 4：第二个测试用例中的多边形 $P,P_1,P_2$ 和 $P_3$，最优亮度已标出。 给定一个凸多边形 $P$，其顶点依次为 $A_1, A_2, \ldots, A_n$。多边形会在 $q$ 步操作中发生变化——在第 $j$ 步，我们删除一个已有顶点，得到新多边形 $P_j$。更精确地说，多边形 $P_j$ 的顶点是尚未删除的 $P$ 的顶点，并且它们的顺序与原多边形 $P$ 相同。可以看出，每个多边形 $P_j$ 仍然是凸的。 请计算初始多边形 $P$ 及每个得到的多边形 $P_1, P_2, \ldots, P_q$ 的最大亮度。

输入的第一行包含正整数 $n$——初始多边形 $P$ 的顶点数。接下来的 $n$ 行，每行包含两个整数 $x_j$ 和 $y_j\ (-10^9\le x_j, y_j \le 10^9)$——顶点 $A_j$ 的坐标。随后一行包含整数 $q\ (0 \le q \le n - 3)$——变化次数。接下来的 $q$ 行，每行包含整数 $k_j\ (1 \le k_j \le n)$，表示第 $j$ 步删除顶点 $A_{k_j}$。可以保证多边形 $P$ 的顶点按逆时针给出，不存在连续平行线，并且所有删除索引 $k_j$ 两两不同。

输出 $q + 1$ 行。第一行输出初始多边形 $P$ 的最大亮度，第 $j\ (1 \le j \le q)$ 行输出第 $j$ 步变更后多边形 $P_j$ 的最大亮度。允许输出结果与标准答案的绝对或相对误差不超过 $10^{−5}$。

### 子任务 ::cute-table{three} |编号 |分数 |限制条件 | |:-:|:--:|:--------:| |$1$|$12$|$n\le 100$| |$2$|$14$|$n\le 2000$| |$3$|$14$|$n\le 100\,000,q=0$| |$4$|$29$|$n\le 100\,000$，对所有 $j = 1,\ldots, q − 1$ 有 $k_j < k_{j+1}$| |$5$|$31$|$n\le 100\,000$| 翻译来源：GPT 4.1 mini。