#P18442. Omniscia Spares None

Omniscia Spares None

Omniscia Spares None

我们的命运笼罩于不确定之中。

穷观之眼将你看透……

世间万物自有其规律……

然而谋略、星座……皆为人类所创!

圣胶鲶鱼(Sanctus Glue-Catfish)的门徒欺骗、压迫平民,掠夺并毁坏了许多珍贵的作品,践踏着人们的努力。

可是穷观阵已经停止运转,符号黯淡,而这些门徒仍未被消灭。符玄想修复穷观阵,却没有可以调遣的人手。她需要你帮助重启穷观阵的阵基终端,并顺路消灭圣胶鲶鱼的怪物。

原题中的符玄与穷观阵

每个阵基终端都可以看作一块棋盘。第 nn 个终端包含 nn 个阵点。为了激活终端,你需要移动地面上的阵点,并连接某些点对,使布局满足:

  • 每个阵点的坐标都是整数,且任意两个阵点的位置不同。
  • 阵点与连边组成一个简单无向图。
  • 每条连边是一条直线段。任意两条连边只能在它们共同的端点处相交,不能在内部相交或重叠。
  • 度数小于 66 的阵点不超过 44 个。

给定 nn,请找出一种满足条件的布局。有多种方案时输出任意一种;不存在时报告无解。

简单无向图不包含重边或自环:任意一对顶点间最多一条边,边的两个端点不能相同。图不额外要求连通。

输入格式

输入一行一个整数 nn,满足 1≤n≤1001\le n\le100。输入只有一个测试实例。

输出格式

如果无解,输出一行 No。

否则,首先输出一行 Yes,然后按照以下格式输出方案:

x1 y1
x2 y2
...
xn yn
m
u1 v1
u2 v2
...
um vm

其中 (xi,yi)(x_i,y_i) 是第 ii 个阵点的坐标,满足 ∣xi∣,∣yi∣≤109|x_i|,|y_i|\le10^9;mm 是连边数量;(uj,vj)(u_j,v_j) 表示连接编号为 uj,vju_j,v_j 的两个阵点,满足 1≤uj,vj≤n1\le u_j,v_j\le n。所有输出的数均须为整数,方案必须满足前述全部条件。

样例 1

3
Yes
-1 0
0 1
1 0
2
1 2
2 3

样例 2

4
Yes
-998244353 -998244353
0 998244353
6 6
1 1
2
1 2
4 3

原题补充示意

下面四种布局也都合法:

合法布局一

合法布局二

合法布局三

合法布局四

下面这种布局不合法,因为连边在线段内部相交:

非法布局:内部相交