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 △TAB 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.
Figure 4: Polygons \(P\), \(P\)1, \(P\)2 and \(P\)3 from the second test case, the optimal brightness is marked.
You are given a convex polygon \(P\) whose vertices are, respectively, points \(A_{1}\), A_{2}, . . . , A_{n}. The polygon is
changed in \(q\) steps — in the \(j\)th 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 \(P\)1, \(P\)2, . . . , \(Pq\).

Subtask 1 (12 points): \(n \le 100\)

Subtask 2 (14 points): \(n \le 2000\)

Subtask 3 (14 points): \(n \le 100\,000\), \(q = 0\)

Subtask 4 (29 points): \(n \le 100\,000\), for each \(j = 1\), . . . , \(q - 1\) it holds \(k_{j} < k_{j}\)_{+1}

Subtask 5 (31 points): \(n \le 100\,000\)

The first line of input contains the positive integer \(n\) — the number of vertices of the initial polygon \(P\).
The \(j\)th of the following \(n\) lines contains two integers \(xj\) and \(yj\) (−\(10^{9} \le xj\), y\(j \le 10^{9}\)) — the coordinates
of vertex \(Aj\). The following line contains the integer \(q\) (\(0 \le q \le n - 3\)) — the number of steps. The \(j\)th
of the following \(q\) lines contains the integer \(kj\) (\(1 \le kj \le n\)) that denotes that in the \(j\)th step we delete
the vertex \(Ak_{j}\). You can assume that the vertices \(Aj\) in polygon \(P\) are given count\(er-cl\)ockwise, that two
consecutive parallel lines do not exist, and that all indices \(kj\) are mutually distinct.

You must output \(q + 1\) lines. The first line must contain the maximal brightness of the initial polygon \(P\),
and the \(j\)th 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.

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Olympiad