QOJ.ac

QOJ

总分: 100 仅输出

#13804. 多边形

统计

一个多边形由其边界上及边界内部的所有点组成。凸多边形具有以下性质:对于多边形内的任意两点 $X$ 和 $Y$,连接 $X$ 和 $Y$ 的线段都在多边形内部。本题中的所有多边形均为至少有两个顶点的凸多边形,且多边形的所有顶点互不相同且具有整数坐标。多边形中没有三点共线。下文中的“多边形”一词均指代此类多边形。

给定两个多边形 $A$ 和 $B$,$A$ 和 $B$ 的闵可夫斯基和(Minkowski sum)由所有形如 $(x_1+x_2, y_1+y_2)$ 的点组成,其中 $(x_1, y_1)$ 是 $A$ 中的一个点,$(x_2, y_2)$ 是 $B$ 中的一个点。事实证明,多边形的闵可夫斯基和也是一个多边形。下图展示了一个例子:两个三角形及其闵可夫斯基和。

两个三角形及其闵可夫斯基和

我们研究闵可夫斯基和的逆运算。对于给定的多边形 $P$,我们寻找两个多边形 $A$ 和 $B$,使得:

  • $P$ 是 $A$ 和 $B$ 的闵可夫斯基和,
  • $A$ 具有 2 到 4 个不同的顶点,即它是一条线段(2 个顶点)、一个三角形(3 个顶点)或一个四边形(4 个顶点),
  • $A$ 应尽可能多地包含顶点,即:
    • 如果可能,$A$ 应为一个四边形,
    • 如果 $A$ 不能是四边形,则如果可能,它应为一个三角形,
    • 否则,它应为一条线段。

显然,$A$ 和 $B$ 都不能等于 $P$,因为那样的话另一个加数就必须是一个点,而点不是一个合法的多边形。

给你一组输入文件,每个文件包含一个多边形 $P$ 的描述。对于每个输入文件,你应该找到满足上述要求的多边形 $A$ 和 $B$,并创建一个包含 $A$ 和 $B$ 描述的输出文件。对于给定的输入文件,总能找到这样的多边形 $A$ 和 $B$。如果存在多个正确的结果,你只需找到并输出其中任意一个。你不需要提交任何程序,只需提交输出文件。

输入格式

你将获得 10 个测试输入文件,分别命名为 polygon1.inpolygon10.in,其中 polygon 后面的数字是输入编号。每个输入文件的组织格式如下。

第一行包含一个整数 $N$:多边形 $P$ 的顶点数。

接下来的 $N$ 行按逆时针顺序描述顶点,每行一个顶点。

第 $I+1$ 行(对于 $I = 1, 2, \dots, N$)包含两个由空格分隔的整数 $X_I$ 和 $Y_I$:多边形第 $I$ 个顶点的坐标。所有输入的坐标均为非负整数。

输出格式

你需要提交 10 个与给定输入文件相对应的输出文件,描述所需的多边形 $A$ 和 $B$。

第一行应包含以下文本:

#FILE polygon I

其中整数 $I$ ($1 \le I \le 10$) 是对应输入文件的编号。

输出格式与输入格式类似。

第二行应包含一个整数 $N_A$:$A$ 的顶点数($2 \le N_A \le 4$)。

接下来的 $N_A$ 行按逆时针顺序描述 $A$ 的顶点,每行一个顶点。

第 $I+2$ 行(for $I = 1, 2, \dots, N_A$)包含两个由空格分隔的整数 $X$ 和 $Y$:多边形 $A$ 的第 $I$ 个顶点的坐标。

第 $N_A+3$ 行应包含一个整数 $N_B$:$B$ 的顶点数($2 \le N_B$)。

接下来的 $N_B$ 行按逆时针顺序描述 $B$ 的顶点,每行一个顶点。

第 $N_A+J+3$ 行(for $J = 1, 2, \dots, N_B$)包含两个由空格分隔的整数 $X$ 和 $Y$:多边形 $B$ 的第 $J$ 个顶点的坐标。

样例

输入 1

5
0 1
0 0
2 0
2 1
1 2

输出 1

#FILE polygon 0
3
0 0
2 0
1 1
2
0 1
0 0

说明 1

对于上述输入,此输出是正确的。此时 $A$ 是一个三角形,且它不能是四边形。

输出 2

#FILE polygon 0
3
0 0
1 0
1 1
3
0 1
0 0
1 0

说明 2

这是另一个正确的输出。


或者逐个上传:

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.