#P18660. LaLa and Magic Circle (LaLa Version)

    ID: 17996 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS不变量分析自定义排序规则叉积扫描线有序集合事件同坐标排序坐标变换

LaLa and Magic Circle (LaLa Version)

LaLa and Magic Circle (LaLa Version)

拉拉的实验室里堆着许多魔法阵。一个魔法阵可以表示为用特殊墨水画出的简单多边形;当且仅当它是凸多边形,也就是所有内角都不大于π时,它才可以使用。

拉拉打算把所有魔法阵都变成可用的,但若修改方式不正确,它们可能失去全部魔力。幸运的是,她有一个恰好能完成这件事的魔法工具。

把一个魔法阵放入工具:如果已经可用,工具便报告这一点;否则,它会选择两个不同的点u、v,满足:

  1. u、v都在这个魔法阵的凸包边界上;
  2. 沿魔法阵边界从u逆时针走到v,除u、v外,这段路径上的所有点都不在魔法阵的凸包边界上。

接着,工具会将这段u—v路径绕u、v中点旋转π。换言之,路径上的每一个点w都会变成 u+v−w,这里的加减逐坐标进行。注意,修改后的图形仍是一个简单多边形。

拉拉嫌工具处理得太慢,为了尽快完成工作去睡觉,她发现:

  1. 对任意魔法阵,使用工具有限次后总能变为可用的魔法阵;
  2. 最终魔法阵所包含的点集与中间的修改选择无关,亦即它的形状和位置都完全由最初的魔法阵决定。

因此,她不必逐次使用工具,而可以直接计算最终的魔法阵,一次完成修改。请写程序帮她求出最终结果。

输入格式

单组输入:

N
x0 y0
x1 y1
...
x(N-1) y(N-1)

最初魔法阵的边界是依次连接(xi,yi)与(x((i+1) mod N),y((i+1) mod N))得到的N条线段的并集。

所有输入满足:

  • 所有数都是整数,3≤N≤100000;
  • 对所有0≤i<N,0≤xi,yi≤300000;
  • 任意两点不同,即i≠j时xi≠xj或yi≠yj;
  • 输入按照一个简单多边形的边界逆时针给出,特别地,边界没有自相交。

输入未禁止连续三个顶点共线。

输出格式

输出:

M
z0 w0
z1 w1
...
z(M-1) w(M-1)

最终魔法阵的边界是依次连接(zi,wi)与(z((i+1) mod M),w((i+1) mod M))得到的M条线段的并集。输出必须满足:

  • 所有输出数都是整数;
  • (z0,w0)的字典序严格小于其他所有顶点:对每个1≤i<M,有z0<zi,或z0=zi且w0<wi;
  • 对任意0≤i<M,循环相邻的(zi,wi)、(z((i+1) mod M),w((i+1) mod M))、(z((i+2) mod M),w((i+2) mod M))不共线;
  • 输出按照一个凸多边形的边界逆时针给出。

可以证明,满足上述要求的输出是唯一的。输出坐标不受输入的0..300000范围限制。

样例输入 1

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

样例输出 1

6
0 2
1 0
6 0
12 3
9 4
3 3

样例说明

最初的魔法阵如下,编号对应输入顺序:

初始魔法阵,原PDF插图

以下展示一种使用工具的过程。虚线表示被修改的路径,它在旋转后变为红色部分。

步骤0

步骤1

步骤2

步骤3

步骤4