一个多边形由其边界上及边界内部的所有点组成。凸多边形具有以下性质:对于多边形内的任意两点 $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.in 到 polygon10.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
这是另一个正确的输出。