{"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- 折线将整块区域分成包含给定整点个数相等的两块。\n- 折线拥有尽可能少的折点。\n\n可以证明一定存在一条满足限制的折线，你只需要输出满足限制的折线的折点数即可。\n\n注意折点的坐标可以不是整数。\n\n## Input\n\n输入第一行一个正整数 $T$，表示数据组数。\n\n接下来的每组数据中，第一行一个**正偶数** $n$，表示给定的整点个数。\n\n接下来 $n$ 行，第 $i$ 行两个正整数 $x_i,y_i$，表示给定的第 $i$ 个整点的坐标为 $(x_i,y_i)$。\n\n## Output\n\n输出 $T$ 行，每行一个正整数，表示满足限制的折线的折点数。\n\n[samples]\n\n## Note\n\n#### 【样例解释】\n\n对于第一组数据，一条合法的折线为：$(0,0) \\to (2.5,0) \\to (2.5,10^{100}) \\to (10^{100},10^{100})$，它有 $(2.5,0)$ 和 $(2.5,10^{100})$ 两个折点。\n\n#### 【数据范围】\n\n|  测试点编号 | $n \\leq$ |      特殊限制      |\n|:-----------:|:--------:|:------------------:|\n|  $1 \\sim 2$ |    $4$   |         无         |\n|  $3 \\sim 4$ |   $10$   |         无         |\n|  $5 \\sim 6$ |   $50$  |         无         |\n|  $7 \\sim 8$ |  $10^5$  | 保证答案不大于 $3$ |\n| $9 \\sim 10$ | $10^5$   | 无                 |\n\n对于所有数据，$1 \\leq T \\leq 10^4, 1 \\leq \\sum n \\leq 5 \\times 10^5, 1 \\leq x_i,y_i \\leq n$，保证 $n$ 为正偶数，每组数据中不存在两个坐标相同的整点。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8858","tags":["洛谷原创","O2优化","洛谷月赛","双指针 two-pointer"],"sample_group":[["3\n4\n1 1\n1 2\n4 1\n4 2\n6\n1 2\n1 3\n2 1\n2 2\n2 3\n3 2\n12\n1 3\n2 2\n2 3\n2 4\n3 1\n3 2\n3 4\n3 5\n4 2\n4 3\n4 4\n5 3\n","2\n3\n4"]],"created_at":"2026-03-03 11:09:25"}}