题目描述

King Byteasar's palace is haunted by a ghost. The spiteful claim it is the ghost of the late Byteasar's wife (who died recently in suspicious circumstances), for it takes great pleasure in looking at itself in the mirror, just as she did. No wonder that Byteasar would gladly get rid of this ghost!

Byteasar has decided to plant a special mirror trap in one of the palace's chambers. It is a closed, well lit room whose every interior wall is covered with mirror. Furthermore, in its every corner a laser gun or a laser detector can be set up. As soon as the ghost crosses one of the laser beams an alarm will go off, summoning Byteasar's ghost vanquishers team (as a royal team, they prefer not to be colloquially called 'ghost busters'), who will surely dispose of the ghost in no time.

The chamber, in which the mirror trap is being installed, is in the shape of a polygon whose consecutive sides are perpendicular. Moreover, the length of every side (measured in metres) is integral. Should a laser gun be installed in some corner, its beam has to be pointed along the bisector of the angle formed by the walls meeting in this corner (in a plane parallel to the floor surface). Obviously, if the laser beam encounters a mirror, it is reflected, obeying the regular reflection law: the angle which the incident ray makes with the normal is equal to the angle which the reflected ray makes to the same normal. This angle, as you may notice, is always 45 degrees due to the chamber's architecture. A beam cast along the bisector into a corner where a detector is placed, is completely absorbed by it. On the other hand, a beam cast along the bisector into corner without a detector (though possibly with a laser gun) is reflected back (by 180 degrees). In all the remaining cases the beam does not change its direction at all.

A maximum number of laser guns complemented with laser detectors should be placed in the room in such a way that each laser beam is eventually absorbed by some detector, no two laser beams are absorbed by the same detector and each detector absorbs some laser beam. Also, a laser gun and a detector may not be placed in the same corner.

An example of a mirror trap with the laser beam going from corner 1 to corner 7:

Write a programme that:

reads from the standard input the the mirror trap's shape description, determines the way of setting up the maximum possible number of laser guns and detectors satisfying the aforementioned conditions, writes out the result to the standard output.

题目大意

题目描述

$N$ 个点的多边形相邻边垂直，边长为整数，边平行坐标轴。要在多边形的点上放一些激光发射器和接收器。满足下列要求：

• 发射器和接收器不能放置在同一点；
• 发射器发出激光可以沿壁反射，最终到达一个接收器；
• 发射器只能沿角平分线发射激光。

求：最多可放置多少对发射器和接收器？$4\leq N\leq 10^5$，多边形周长不超过 $3\times 10^5$。

输入格式

第一行给出一个数字 $N$，代表有多少个点。下面 $N$ 行,用来描述点的坐标.其值在 $[-1000000,1000000]$。

输出格式

第一行一个数，最多可放置多少对发射器和接收器。接下来若干行，每行两个数，描述一对发射器和接收器。

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