3450. 华生的围栏

单点时限: 1.0 sec

内存限制: 256 MB

唐纳德的朋友华生曾经造过一个围栏。华生可能是一个专精于计算几何的计算机科学家,因为下列事实绝非巧合:

  • 围栏是一个凸 $n$ ($3 \le n \le 100$) 边形,换而言之多边形的每个内角都不超过 $180$ 度;

  • 可以将围栏放置在一个 $xOy$ 平面内,使得多边形的所有顶点 $(x_0,y_0), (x_1,y_1), \ldots, (x_{n-1},y_{n-1})$ 都是整数点对;

  • 多边形的周长 $C = \sum_{i=0}^{n-1} \sqrt{(x_i-x_{i+1})^2+(y_i-y_{i+1})^2}$ 也是一个整数。

但是因为某些历史原因,这个围栏已经被摧毁了。目前只能从模糊的史料中辨认出围栏的周长 $C$。试将围栏复原,或者报告不可能。

输入格式

输入一个整数 $C$ ($1 \le C \le 201~712$)。

输出格式

如果不可能,输出 $-1$。否则:

  • 输出第一行包含一个整数 $n$ ($3 \le n \le 100$)。
  • 接下来 $n$ 行以逆时针的顺序给出一个凸多边形。多边形的点坐标应满足是在 $0$ 到 $1~000~000$ 之间的整数。

换而言之具有如下的形式:

$n \
x_1 \ y_1 \
x_2 \ y_2 \
\vdots \
x_n \ y_n$

样例

Input
12
Output
3
0 0
3 0
0 4

54 人解决,60 人已尝试。

55 份提交通过,共有 132 份提交。

3.3 EMB 奖励。

创建: 2 年,7 月前.

修改: 2 年,5 月前.

最后提交: 1 月,2 周前.

来源: EOJ Monthly 2018.1

题目标签