COI '17 #3 Svjetlost

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 3.0s
Memory limit: 1G

Problem types

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 \overline{AB} is lit up if the area of the triangle \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, \dots, A_n. The polygon is changed in q steps — in the j^\text{th} step, we delete an existing polygon vertex, and obtain a new polygon P_j. More precisely, the vertices of polygon P_j 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 P_j is convex too.

Determine the maximal brightness of the polygon P and each of the obtained polygons P_1, P_2, \dots, P_q.

Input Specification

The first line of input contains the positive integer n — the number of vertices of the initial polygon P.

The j^\text{th} of the following n lines contains two integers x_j and y_j (-10^9 \le x_j, y_j \le 10^9) — the coordinates of vertex A_j. The following line contains the integer q (0 \le q \le n-3) — the number of steps. The j^\text{th} of the following q lines contains the integer k_j (1 \le k_j \le n) that denotes that in the j^\text{th} step we delete the vertex A_{k_j}. You can assume that the vertices A_j in polygon P are given counter-clockwise, that two consecutive parallel lines do not exist, and that all indices k_j are mutually distinct.

Output Specification

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

Constraints

SubtaskPointsConstraints
112n \le 100
214n \le 2\,000
314n \le 100\,000, q = 0
429n \le 100\,000, for each j = 1, \dots, q-1 it holds k_j < k_{j+1}
531n \le 100\,000

Sample Input 1

4
0 0
10 0
10 10
0 10
1
2

Sample Output 1

20.000000
24.142136

Sample Input 2

6
2 2
4 0
6 0
8 2
8 4
2 4
3
1
4
3

Sample Output 2

10.828427
11.300563
10.944272
11.656854

Comments

There are no comments at the moment.