In a plane, if we have a convex polygon , and we place a source of light at a point located outside the polygon, it lights up some edges of — if and are two consecutive polygon vertices, then the edge is lit up if the area of the triangle 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 . The distance between point and the polygon can be arbitrary, and the coordinates of point don't necessarily need to be integers.
You are given a convex polygon whose vertices are, respectively, points . The polygon is changed in steps — in the step, we delete an existing polygon vertex, and obtain a new polygon . More precisely, the vertices of polygon are the vertices of that haven't been deleted yet, and their order is the same as in polygon . It is easy to see that each polygon is convex too.
Determine the maximal brightness of the polygon and each of the obtained polygons .
Input Specification
The first line of input contains the positive integer — the number of vertices of the initial polygon .
The of the following lines contains two integers and — the coordinates of vertex . The following line contains the integer — the number of steps. The of the following lines contains the integer that denotes that in the step we delete the vertex . You can assume that the vertices in polygon are given counter-clockwise, that two consecutive parallel lines do not exist, and that all indices are mutually distinct.
Output Specification
You must output lines. The first line must contain the maximal brightness of the initial polygon , and the of the following lines must contain the maximal brightness of polygon obtained after steps. For each line of output, an absolute and relative deviation from the official solution by will be tolerated.
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 12 | |
2 | 14 | |
3 | 14 | , |
4 | 29 | , for each it holds |
5 | 31 |
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