折线

题目描述

平面直角坐标系的第一象限内有一块左下角为 \((0,0)\) 右上角为 \((10^{100},10^{100})\) 的矩形区域，区域内有正偶数个整点，试求出这样一条从 \((0,0)\) 出发，到 \((10^{100},10^{100})\) 的在区域内部的折线：

• 折线的每一部分都平行于 \(x\) 轴或 \(y\) 轴。
• 折线不能经过给定的整点。
• 折线将整块区域分成包含给定整点个数相等的两块。
• 折线拥有尽可能少的折点。

可以证明一定存在一条满足限制的折线，你只需要输出满足限制的折线的折点数即可。

注意折点的坐标可以不是整数。

输入格式

输入第一行一个正整数 \(T\)，表示数据组数。

接下来的每组数据中，第一行一个正偶数 \(n\)，表示给定的整点个数。

接下来 \(n\) 行，第 \(i\) 行两个正整数 \(x_i,y_i\)，表示给定的第 \(i\) 个整点的坐标为 \((x_i,y_i)\)。

输出格式

输出 \(T\) 行，每行一个正整数，表示满足限制的折线的折点数。

样例 #1

样例输入 #1

3
4
1 1
1 2
4 1
4 2
6
1 2
1 3
2 1
2 2
2 3
3 2
12
1 3
2 2
2 3
2 4
3 1
3 2
3 4
3 5
4 2
4 3
4 4
5 3

样例输出 #1

2
3
4

提示

【样例解释】

对于第一组数据，一条合法的折线为：\((0,0) \to (2.5,0) \to (2.5,10^{100}) \to (10^{100},10^{100})\)，它有 \((2.5,0)\) 和 \((2.5,10^{100})\) 两个折点。

【数据范围】

对于所有数据，\(1 \leq T \leq 10^4, 1 \leq \sum n \leq 5 \times 10^5, 1 \leq x_i,y_i \leq n\)，保证 \(n\) 为正偶数，每组数据中不存在两个坐标相同的整点。

题解

引理1:折点数量在\([2,4]\)之间

证明:(从x轴考虑,y轴同理)

考虑找到一个\(a\)使得\(x\)坐标小于\(a\)的和\(x\)坐标大于\(a\)的点的数量不超过\(\frac{n}{2}\)(先预处理每个\(x\)坐标的点的数量,再做一遍前缀和即可求出)

那么考虑将直线\(x=a\)划分为两个部分,自底向上最多折3次即可达到划分目的,最后一次是当折线的坐标到了\((a,10^{100})\)的时候再折到终点,故上界是4

而需要划分点,至少需要折一次,然后还得再折一次到终点,故下界是2

引理2:

折两次的充要条件为存在一个\(a\),使得\(x\)坐标小于\(a\)或\(y\)坐标小于\(a\)的点的数量为\(\frac{n}{2}\),证明显然

引理3

折3次的充要条件为存在一个矩形\((1,i,i,n)\)或\((i,1,n,j)\)使得矩形值为\(n/2\)

因为折两次只有两种图形(如下),证明显然

所以问题就变成了判断是否存在矩形\((1,i,j,n)\)或\((i,1,n,j)\)使得矩形值为\(n/2\),采用悬线法解决

可以这样考虑,因为折三次可以分为从x折第一次还是从y折,下面讨论从\(x\)折,处理矩形\((i,1,n,j)\)的方法

代码应该比较好懂,没看懂可以私信我

//fc D:\编程\C++\ex_line2.out D:\编程\C++\ex_line2.ans
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 5000050
struct node {
	int x, y;
}a[N];
inline int read(void) {
	int x = 0, f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-') f = -1;
	for (; isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}
int f1[N], f2[N], g1[N], g2[N], n, m, q;
vector<int>s1[N], s2[N];
inline void init() {
	for (int i = 1; i <= n; i++)f1[i] = f2[i] = g1[i] = g2[i] = a[i].x = a[i].y = 0;
	for (int i = 1; i <= n; i++) {
		s1[i].clear();
		s2[i].clear();
	}
	n = read();
	for (int i = 1; i <= n; i++) {
		int x, y;
		x = read(); y = read();
		g1[x]++, g2[y]++;
		a[i].x = x, a[i].y = y;
		s1[x].push_back(i);
		s2[y].push_back(i);
	}
}
inline bool check2() {
	for (int i = 1, j = 0, k = 0; i <= n; i++) {
		j += g1[i];
		k += g2[i];
		if (j == n / 2 || k == n / 2)return true;
	}
	return false;
}
inline bool check3_1() {
	//第一部分，判断矩形(i,1,n,j)
	int l = 1, r = 1, m = 0;
	while (l <= n) {
		while (m < n / 2 && r <= n) {
			m += g2[r] - f2[r];
			//		printf("A %d %d %d\n", l, r, m);
			r++;
		}
		if (m == n / 2)return true;
		int len = s1[l].size();
		for (int i = 0; i < len; i++) {
			f2[a[s1[l][i]].y]++;
			if (a[s1[l][i]].y < r)m--;
		}
		l++;
	}
	if (m == n / 2)return true;
	return false;
}
inline bool check3_2() {
	int l = 1, r = 1, m = 0;
	while (l <= n) {
		while (m < n / 2 && r <= n) {
			m += g1[r] - f1[r];
			//		printf("A %d %d %d\n", l, r, m);
			r++;
		}
		if (m == n / 2)return true;
		int len = s2[l].size();
		for (int i = 0; i < len; i++) {
			f1[a[s2[l][i]].x]++;
			if (a[s2[l][i]].x < r)m--;
		}
		l++;
	}
	if (m == n / 2)return true;
	return false;
}
int main() {
	//	freopen("ex_line2.in","r",stdin);
	//	freopen("ex_line2.ans","w",stdout);
	int t = read();
	while (t--) {
		init();
		if (check2()) {
			puts("2");
			continue;
		}
		if (check3_1() || check3_2()) {
			puts("3");
			continue;
		}
		puts("4");
	}
}