题目描述

题目译自 XV OI Olimpiada Informatyczna – I etap Szklana pułapka

Bajtazar 国王的宫殿闹鬼。传言这是他新丧妃子（死因可疑）的灵魂，因其生前爱照镜子，鬼魂也常在镜中现身。Bajtazar 急欲驱除此鬼。

他决定在一间宫室中布置玻璃陷阱。这是一间密闭、灯光明亮的房间，内壁全部覆以镜面。每个角可放置激光器或光线传感器。一旦鬼魂触碰激光束，警报将触发，Bajtazar 召来的驱鬼者即可出手。

陷阱房间为多边形，相邻墙壁垂直，每个墙长度（米）为整数。若某角放置激光器，其光束须沿该角墙壁夹角的角平分线发射（平行于地面）。光束遇镜面以 45 度角反射；若沿角平分线射入带传感器的角，光束被传感器完全吸收；若射入无传感器的角（可能有另一激光器），光束 180 度反射；其他情况下，光束保持方向继续传播。

需在房间角点布置尽可能多的激光器和对应传感器，确保：每个激光器光束射入某传感器；不同激光器光束射入不同传感器；每个传感器接收某激光器光束。每个角仅可装激光器或传感器，不可以都装。

编写程序：

• 从标准输入读取玻璃陷阱形状描述。
• 确定满足条件的最多激光器-传感器对布置方案。
• 将结果输出到标准输出。

输入格式

第一行包含一个整数 $n$ $(4 \leq n \leq 100000)$，表示陷阱墙壁数。接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ $(-1000000 \leq x_i, y_i \leq 1000000)$，用单个空格分隔，表示第 $i$ $(1 \leq i \leq n)$ 角的坐标。相邻角由平行坐标轴的墙壁连接。墙壁不交叉，仅相邻墙壁在公共角点接触。角点按顺时针顺序给出（沿墙内侧行走，房间内部始终在右侧）。所有墙壁总长度不超过 $300000$。

输出格式

第一行输出一个整数 $m$，表示可布置的最大激光器-传感器对数。接下来的 $m$ 行，每行包含两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n)$，用单个空格分隔，$a_i$ 表示放置激光器的角编号，$b_i$ 表示对应传感器的角编号。若存在多种方案，输出任意一种。

10
1 1
3 1
3 -2
-3 -2
-3 0
-1 0
-1 -1
2 -1
2 0
1 0

5
10 5
1 7
2 9
3 8
4 6