P8858 折线
题目描述
平面直角坐标系的第一象限内有一块左下角为 $(0,0)$ 右上角为 $(10^{100},10^{100})$ 的矩形区域,区域内有**正偶数**个整点,试求出这样一条从 $(0,0)$ 出发,到 $(10^{100},10^{100})$ 的在区域内部的折线:
- 折线的每一部分都平行于 $x$ 轴或 $y$ 轴。
- 折线不能经过给定的整点。
- 折线将整块区域分成包含给定整点个数相等的两块。
- 折线拥有尽可能少的折点。
可以证明一定存在一条满足限制的折线,你只需要输出满足限制的折线的折点数即可。
注意折点的坐标可以不是整数。
输入格式
无
输出格式
无
说明/提示
#### 【样例解释】
对于第一组数据,一条合法的折线为:$(0,0) \to (2.5,0) \to (2.5,10^{100}) \to (10^{100},10^{100})$,它有 $(2.5,0)$ 和 $(2.5,10^{100})$ 两个折点。
#### 【数据范围】
| 测试点编号 | $n \leq$ | 特殊限制 |
|:-----------:|:--------:|:------------------:|
| $1 \sim 2$ | $4$ | 无 |
| $3 \sim 4$ | $10$ | 无 |
| $5 \sim 6$ | $50$ | 无 |
| $7 \sim 8$ | $10^5$ | 保证答案不大于 $3$ |
| $9 \sim 10$ | $10^5$ | 无 |
对于所有数据,$1 \leq T \leq 10^4, 1 \leq \sum n \leq 5 \times 10^5, 1 \leq x_i,y_i \leq n$,保证 $n$ 为正偶数,每组数据中不存在两个坐标相同的整点。