← 返回题目列表

Codeforces · 1666/G

G. 全球变暖

中文机器翻译题面 查看原题

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

Global Warming - 原题 PDF 第 1 页
原题PDF第7页
Global Warming - 原题 PDF 第 2 页
原题PDF第8页
Global Warming - 原题 PDF 第 3 页
原题PDF第9页
可复制的 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