시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 8 | 4 | 4 | 80.000% |
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 4T AB 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, P1, P2 and P3 from the second test case, the optimal brightness is marked.
You are given a convex polygon P whose vertices are, respectively, points A1, A2, . . . , An. The polygon is changed in q steps — in the jth 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 P1, P2, . . . , Pq.
The first line of input contains the positive integer n — the number of vertices of the initial polygon P. The jth of the following n lines contains two integers xj and yj (−109 ≤ xj, yj ≤ 109) — the coordinates of vertex Aj. The following line contains the integer q (0 ≤ q ≤ n − 3) — the number of steps. The jth of the following q lines contains the integer kj (1 ≤ kj ≤ n) that denotes that in the jth step we delete the vertex Akj . You can assume that the vertices Aj in polygon P are given counter-clockwise, 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 jth 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.
번호 | 배점 | 제한 |
---|---|---|
1 | 12 | n ≤ 100 |
2 | 14 | n ≤ 2000 |
3 | 14 | n ≤ 100 000, q = 0 |
4 | 29 | n ≤ 100 000, for each j = 1, . . . , q − 1 it holds kj < kj+1 |
5 | 31 | n ≤ 100 000 |
4 0 0 10 0 10 10 0 10 1 2
20.000000 24.142136
6 2 2 4 0 6 0 8 2 8 4 2 4 3 1 4 3
10.828427 11.300563 10.944272 11.656854
Olympiad > Croatian Highschool Competitions in Informatics > 2018 > Croatian Olympiad in Informatics 2018 3번