← 返回题目列表

Codeforces · 2122/F

F. 彩色多边形

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

给定一个数组 $$$a_1, a_2, \ldots, a_n$$$,其中 $$$n \leq 8$$$ 和 $$$a_1 + a_2 + \cdots + a_n \leq 100$$$。

构造一个简单的多边形$$$^{\text{*}}$$$,最多有 $$$333$$$ 个顶点,并且恰好有 $$$$$$\frac{(a_1 + a_2 + \cdots + a_n)!}{a_1! a_2! \cdots a_n!}$$$$$$不同的三角剖分$$$^{\text{†}}$$$。可以证明这样的多边形总是存在的。

$$$^{\text{*}}$$$简单多边形是不与自身相交并且没有孔的多边形。换句话说,任何两条不连续的边都不能有公共点,并且连续的边必须恰好有一个公共点——它们之间的顶点。连续的边可以是共线的。

$$$^{\text{†}}$$$具有 $$$m$$$ 顶点的多边形的三角剖分是一组仅在顶点相交的 $$$m-3$$$ 对角线。对角线是位于多边形内部两个顶点之间的线段,并且与多边形边有两个公共点(它连接的顶点)。

输入

每个测试的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 8$$$) — 数组中的元素数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$) — 数组的元素。

保证 $$$a_1 + a_2 + \cdots + a_n$$$ 不超过 $$$100$$$。

输出

在第一行中,输出单个整数 $$$m$$$ ($$$3 \leq m \leq 333$$$) — 多边形中的顶点数。

在接下来的 $$$m$$$ 行的第 $$$i$$$ 行中,输出两个整数 $$$x_i$$$, $$$y_i$$$ ($$$-10^6 \leq x_i, y_i \leq 10^6$$$) – 多边形第 $$$i$$$ 顶点的坐标。

多边形必须是简单的。顶点可以按顺时针或逆时针顺序给出。

示例

输入
复制

3
1 1 2

输出
复制

8
0 0
2 1
4 2
6 1
3 5
4 7
0 5
1 2

输入
复制

2
4 1

输出
复制

5
-2 -2
-3 1
0 3
3 1
2 -2

注意

在第一个测试中,所需的多边形必须具有 $$$\tfrac{4!}{1! 1! 2!} = 12$$$ 三角剖分。以下是示例多边形的所有三角剖分。

在第二个测试中,所需的多边形必须具有 $$$\tfrac{5!}{4! 1!} = 5$$$ 三角剖分。