#P18660. LaLa and Magic Circle (LaLa Version)
LaLa and Magic Circle (LaLa Version)
LaLa and Magic Circle (LaLa Version)
拉拉的实验室里堆着许多魔法阵。一个魔法阵可以表示为用特殊墨水画出的简单多边形;当且仅当它是凸多边形,也就是所有内角都不大于π时,它才可以使用。
拉拉打算把所有魔法阵都变成可用的,但若修改方式不正确,它们可能失去全部魔力。幸运的是,她有一个恰好能完成这件事的魔法工具。
把一个魔法阵放入工具:如果已经可用,工具便报告这一点;否则,它会选择两个不同的点u、v,满足:
- u、v都在这个魔法阵的凸包边界上;
- 沿魔法阵边界从u逆时针走到v,除u、v外,这段路径上的所有点都不在魔法阵的凸包边界上。
接着,工具会将这段u—v路径绕u、v中点旋转π。换言之,路径上的每一个点w都会变成 u+v−w,这里的加减逐坐标进行。注意,修改后的图形仍是一个简单多边形。
拉拉嫌工具处理得太慢,为了尽快完成工作去睡觉,她发现:
- 对任意魔法阵,使用工具有限次后总能变为可用的魔法阵;
- 最终魔法阵所包含的点集与中间的修改选择无关,亦即它的形状和位置都完全由最初的魔法阵决定。
因此,她不必逐次使用工具,而可以直接计算最终的魔法阵,一次完成修改。请写程序帮她求出最终结果。
输入格式
单组输入:
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
样例说明
最初的魔法阵如下,编号对应输入顺序:

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




