以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
ICPC 2021–2022, NERC – Northern Eurasia Finals
St. Petersburg, Almaty, Barnaul, Minsk, Yerevan, April 13th, 2022
Problem G. Global Warming
Time limit: 3 seconds
Memory limit: 512 megabytes
You are developing a new computer game. Let’s consider an island in the middle of the ocean in a three-
dimensional space with z-axis pointing upwards. The surface of the ocean is a horizontal plane with z = 0.
The island is a polyhedron of a special form.
You are given n points (xi, yi, zi); there are some edges between them. If we look at the island from above
or if we discard z coordinate of each point, points and edges form a planar connected graph. Every face of
this planar graph, except the external one, is a nondegenerate triangle. Every edge of the graph belongs
to at least one internal face. All points that lie on the edge of the external face of the graph have z
coordinates equal to zero. Other points may have arbitrary non-negative z coordinates. Every face of the
planar graph corresponds to the face of the polyhedron with the same vertices.
Due to global warming, the level of the ocean is increasing and floods the island. Your task is to compute
various global warming scenarios for the game.
In each scenario, the level of the ocean increased to the height h, so that the surface of the ocean is a
plane z = h. Parts of the island that are below or at the height h are now flooded, even though some
parts may be not reachable from the ocean by water (see the illustration for the second example). In a
scenario, a player is standing in p-th point. You shall compute the area of the surface of the part of the
island where the player is standing, or determine that the player is standing at or below the water level
and has drowned.
Formally, we say that two points on the surface of the island belong to the same part if a player can move
between them walking by the surface of the island staying strictly higher than ocean level. Note that you
should find the area of the surface of the island itself, not the area of its projection on a horizontal plane.
Input
The first line contains a single integer n — the number of points (1 ≤n ≤105).
Each of the next n lines contains three integers xi, yi, and zi — the coordinates of i-th point
(−106 ≤xi, yi ≤106; 0 ≤zi ≤106).
The next line contains a single integer m — the number of internal faces of the planar graph (1 ≤m ≤105).
They are also the faces of the island’s polyhedron.
Each of the next m lines contains three integers ai, bi, and ci — the indices of three points that are vertices
of i-th internal face (1 ≤ai, bi, ci ≤n).
It is guaranteed that if z coordinate is discarded, then the resulting graph is a connected and planar
graph. All its faces, except the external one, are nondegenerate triangles. All points that lie on the edge
of the external face of the planar graph have z coordinate equal to zero.
The next line contains an integer q — the number of global warming scenarios to compute (1 ≤q ≤105).
Each of the next q lines contains two integers hi and pi — the level of the ocean and the index of the
point where the player is standing respectively (0 ≤hi ≤106; 1 ≤pi ≤n).
Output
For every scenario output a single real number — the area of the surface of part of the island where the
player is standing. If the player’s position is flooded by water, output −1 instead.
The answer is considered correct if its absolute or relative error does not exceed 10−6.
Examples
The illustrations of the examples are views of the island from the above. The ocean is hatched. The island
is drawn with contour lines, with higher parts in darker colors.
Page 7 of 16
ICPC 2021–2022, NERC – Northern Eurasia Finals
St. Petersburg, Almaty, Barnaul, Minsk, Yerevan, April 13th, 2022
standard input standard output illustration
5 -1
0 0 0 16.492422502470642
2 0 0 9.276987657639736
Ocean
2 2 0 4.123105625617661
level
0 2 0 1.030776406404415
z = 0
1 1 4 -1
4 -1
1 2 5
2 3 5
3 4 5 Ocean
4 1 5 level
7 z = 1
0 1
0 5
1 5
2 5
Ocean 3 5
level 4 5
z = 2 5 5
Ocean
level
z = 3
See the second example on the next page.
The island in the second example looks as follows.
Page 8 of 16
ICPC 2021–2022, NERC – Northern Eurasia Finals
St. Petersburg, Almaty, Barnaul, Minsk, Yerevan, April 13th, 2022
standard input standard output illustration
16 120.483405354306325
0 5 0 -1
1 2 0 93.929895222484783
2 5 5 68.181919663536940
3 7 0 40.918561474148331 Ocean
4 0 0 11.067441790921070 level
4 3 5 -1 z = 0
5 5 1
6 2 0
6 6 5
7 4 4
7 8 0
8 2 0
9 4 0
4 6 4 Ocean
6 3 3 level
2 4 5 z = 1
22
11 10 9
12 8 10
2 6 5
9 10 7
8 15 6
16 3 6
Ocean15 6 7
level7 3 14
z = 28 10 15
11 13 10
16 6 2
12 10 13
10 7 15
16 3 2
3 4 1
14 7 9
Ocean
11 9 4
level
3 6 7
z = 3
5 6 8
14 4 3
3 1 2
9 4 14
7
0 7
1 7
1 16 Ocean
2 10 level
3 9 z = 4
4 16
5 16
Page 9 of 16