折线

Luogu

IDLGP8858

Time1000ms

Memory512MB

DifficultyP4

洛谷原创O2优化洛谷月赛双指针 two-pointer

平面直角坐标系的第一象限内有一块左下角为 $(0,0)$ 右上角为 $(10^{100},10^{100})$ 的矩形区域，区域内有**正偶数**个整点，试求出这样一条从 $(0,0)$ 出发，到 $(10^{100},10^{100})$ 的在区域内部的折线： - 折线的每一部分都平行于 $x$ 轴或 $y$ 轴。 - 折线不能经过给定的整点。 - 折线将整块区域分成包含给定整点个数相等的两块。 - 折线拥有尽可能少的折点。可以证明一定存在一条满足限制的折线，你只需要输出满足限制的折线的折点数即可。注意折点的坐标可以不是整数。 ## Input 输入第一行一个正整数 $T$，表示数据组数。接下来的每组数据中，第一行一个**正偶数** $n$，表示给定的整点个数。接下来 $n$ 行，第 $i$ 行两个正整数 $x_i,y_i$，表示给定的第 $i$ 个整点的坐标为 $(x_i,y_i)$。 ## Output 输出 $T$ 行，每行一个正整数，表示满足限制的折线的折点数。 [samples] ## Note #### 【样例解释】对于第一组数据，一条合法的折线为：$(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$ 为正偶数，每组数据中不存在两个坐标相同的整点。

Samples

Input #1

Output #1

2
3
4

API Response (JSON)

{
  "problem": {
    "name": "折线",
    "description": {
      "content": "平面直角坐标系的第一象限内有一块左下角为 $(0,0)$ 右上角为 $(10^{100},10^{100})$ 的矩形区域，区域内有**正偶数**个整点，试求出这样一条从 $(0,0)$ 出发，到 $(10^{100},10^{100})$ 的在区域内部的折线： - 折线的每一部分都平行于 $x$ 轴或 $y$ 轴。 - 折线不能经过给定的整点。 - 折线将整块区域分成包含给定整点个数相等的两块",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8858"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "平面直角坐标系的第一象限内有一块左下角为 $(0,0)$ 右上角为 $(10^{100},10^{100})$ 的矩形区域，区域内有**正偶数**个整点，试求出这样一条从 $(0,0)$ 出发，到 $(10^{100},10^{100})$ 的在区域内部的折线：\n\n- 折线的每一部分都平行于 $x$ 轴或 $y$ 轴。\n- 折线不能经过给定的整点。\n- 折线将整块区域分成包含给定整点个数相等的两块...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments