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


可复制的 PDF 提取文本
Problem B
Three-Dimensional Embedding
Time limit: 2 seconds
An embedding of a graph in a space is a way of placing each vertex at a distinct point in that space and drawing each
edge as a simple arc connecting its two vertices, so that no two arcs intersect except at a shared vertex. In this problem,
we focus on embeddings in a three-dimensional space under certain conditions.
You are given a simple undirected graph with n vertices and m edges, which means there is at most one edge con-
necting any pair of vertices and each edge connects different vertices. The vertices are numbered from 1 to n, and the
edges are numbered from 1 to m. Edge j connects the two distinct vertices vj and wj. Each vertex is incident to at
most five edges.
Find an embedding of the graph such that all of the following conditions are satisfied.
• Each vertex i is embedded as a point (xi, yi, 0) in the space. The coordinates xi and yi must be integers between
0 and 400, inclusive. All points must have distinct coordinates.
• Each edge j is embedded as a polyline (a connected series of line segments) with the embedded points for
vertices vj and wj as its endpoints. Each segment of the polyline must be parallel to the x-, y-, or z-axis. Each
node of the polyline must have integer coordinates between 0 and 400, inclusive. Each polyline must have no
more than 30 nodes, counting its endpoints.
• Polylines must not have self-intersections. Distinct polylines must not share any point, except when they corre-
spond to edges incident to the same vertex. In that case, they may share only that single endpoint.
Input
The first line of input contains two integers n and m (2 ≤n ≤1600, 1 ≤m ≤4000). The j-th of the following m
lines contains two integers vj and wj (1 ≤vj < wj ≤n).
The input guarantees that each vertex is incident to at most five edges. Further, there are no parallel edges; that is, if
j ̸= j′, (vj, wj) ̸= (vj′, wj′) holds.
Output
First, output n lines. The i-th of these lines should contain two integers xi and yi, representing the coordinates where
vertex i is embedded. Then, output m lines, where the j-th line represents the polyline corresponding to edge j, using
the following format:
k x′1 y′1 z′1 · · · x′k y′k z′k
Here, k is the number of nodes, which must be between 2 and 30, inclusive. The points (x′1, y′1, z′1), . . . , (x′k, y′k, z′k)
are the nodes of the polyline. The first point (x′1, y′1, z′1) must be (xvj, yvj, 0), and the last point (x′k, y′k, z′k) must be
(xwj, ywj, 0). Each pair of consecutive points is connected by a segment to form the polyline. Each segment must
have a positive length. Two consecutive segments may have the same orientation; for example, both can be parallel to
the x-axis.
The embedding that you output must satisfy all of the conditions mentioned above.
The 2025 ICPC Asia Pacific Championship Problem B: Three-Dimensional Embedding
Under the given input constraints, it can be shown that there exists at least one valid output. If there are multiple
outputs, any one of them will be accepted.
Notes on special judging:
You are provided with a command-line tool for local testing. You can download the file from DOMjudge. The tool
has comments at the top to explain its use.
Sample Input #1 Sample Output #1
3 3 0 0
1 2 400 0
1 3 0 399
2 3 3 0 0 0 100 0 0 400 0 0
4 0 0 0 0 0 200 0 399 200 0 399 0
3 400 0 0 400 399 0 0 399 0
Explanation for the sample input/output #1
Figure B.1 illustrates the embedding represented by the sample output.
400
300
Z 200
Vertex 3
100
0
400
Vertex 1 300
0 200
100 Y Vertex 2 200 100
X 300
400 0
Figure B.1: Illustration of the embedding.
The 2025 ICPC Asia Pacific Championship Problem B: Three-Dimensional Embedding