自动搬运

查看原文

来自洛谷，原作者为

	__gcd **

搬运于2025-08-24 22:27:06，当前版本为作者最后更新于2021-01-29 17:43:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

标签：平面坐标+双指针

思考+调试总共耗时7h，写篇题解纪念一下。

基本思路

• 第一种情况，空集或者只包含一个点。

显然，答案为 $n+1$。

• 第二种情况，包含两个及以上的点。

枚举正方形最左和最右的两个点 $i,j(i<j)$，满足 $|x_i-x_j|\geq |y_i-y_j|$，则正方形的边长 $side=|x_i-x_j|$。对于 $|x_i-x_j|\leq |y_i-y_j|$ 的情况，可以通过交换每个点的 $x,y$ 坐标再通过相同的方式得到答案，这里就不再讨论。

对所有坐标以 $x$ 坐标为第一关键字，$y$ 坐标为第二关键字排序。排序之后，正方形中所有点的下标必定在 $[i,j]$ 之间，$x$ 坐标必定在 $[x_i,x_j]$ 之间。

考虑 $y$ 坐标，不妨将下标在 $[i,j]$ 之间的点的 $y$ 坐标排序后放在一个长度为 $j-i+1$ 的数组 $v$ 中。这样，正方形中的点的 $y$ 坐标一定属于数组 $v$ 的一个连续区间。问题转变为了求出这个区间的两端点 $l,r$ 有多少种组合方式。因为 $v$ 数组有序，所以可以使用双指针来解决这个问题。

双指针的具体实现

这里的双指针类似于滑动一个长度为 $side$ 的窗口。

首先确定 $v_l$ 和 $v_r$ 的范围。因为正方形必须包含 $i,j$ 两点，所以设 $mini=\max(y_i,y_j)-side$，$maxi=\min(y_i,y_j)$，那么正方形的下边界 $lower\in[mini,maxi]$，上边界 $upper\in[mini+side,maxi+side]$。

注：上边界和下边界并不代表 $v_l$ 和 $v_r$。

接下来讨论什么样的 $[l,r]$ 是合法的。需要满足以下两个条件。

• 正方形必须能同时包含 $v_l$ 和 $v_r$ 两个坐标，即 $v_l\leq v_r-side$。

• 正方形不能包括 $v_{r+1}$，同样不能包括 $v_{l-1}$。

  这个条件的讨论有一些复杂。不妨固定右端点 $r$，去寻找可行的左端点。

  包含 $v_r$ 且不包含 $v_{r+1}$，正方形的上边界需要满足 $upper\in[v_r,v_{r+1}-1]$，对应到下边界就是 $lower\in[v_r-side,v_{r+1}-1-side]$。要使 $l$ 合法，则需 $\exists lower[v_r-side,v_{r+1}-1-side]$，使得 $lower>v_{l-1}$。那么只要使 $lower$ 的最大值 $v_{r+1}-1-side>v_{l-1}$ 即可。

  所以只要满足 $v_{r+1}-1-side>v_{l}$ 便可将指针 $l$ 向右移动一位，即 $l\gets l+1$。

最后还有 $|x_i-x_j|\geq |y_i-y_j|$ 和 $|x_i-x_j|\leq |y_i-y_j|$ 出现重复的问题。如果在统计的时候出现 $v_r-v_l=side$ 的情况，那么当 $l,r$ 对应的下标成为下一轮枚举的 $i,j$ 时，这个正方形中包含的子集会被再统计一次，减去即可。

这道题还有很多的细节，详情请见代码。（当然你问我为什么代码显示不全，是因为代码太宽了233，只需要复制到编辑器里就可以看了）

#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
inline int read() {
	int x = 0; bool op = false;
	char c = getchar();
	while(!isdigit(c))op |= (c == '-'), c = getchar();
	while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return op ? -x : x;
}
const int N = 210;
int n, ans, res;
struct Node {
	int x, y;
	bool operator < (const Node &tmp) const {
		if(x ^ tmp.x)return x < tmp.x;
		else return y < tmp.y;
	}
	Node(int x = 0, int y = 0):x(x), y(y){}
}a[N];
set<int> s;
void solve() {
	sort(a + 1, a + 1 + n);
	for(int i = 1; i < n; i++) {
		s.clear(); s.insert(a[i].y);
		for(int j = i + 1; j <= n; j++) {
			s.insert(a[j].y);
			vector<int> vec(s.begin(), s.end()); //从题解里面学到的奇怪操作，相当于把s中的元素复制到了vec里 
			int side = a[j].x - a[i].x;
			int mini = max(a[i].y, a[j].y) - side, maxi = min(a[i].y, a[j].y);
			if(mini > maxi)continue; //如果下界在上界之上，直接跳过 
			int len = vec.size(), l = 0, r = -1;
			while(r + 1 < len && vec[r + 1] < mini + side)r++; 
			//找到最大的r，使得vec[r]<mini+side
			//之所以要这么找，是因为可能存在上界在[mini+side,maxi+side]之中但是vec[r]不在这个区间之中的情况
			//那么包含它且不包含vec[r+1]的条件也有所转变，即上界在[mini+side,vec[r+1]-1]之间。 
			while(l < len && vec[l] < mini)l++; //找到最小的l，使vec[l]>=mini 
			for(; r < len && (r < 0 || vec[r] <= maxi + side); r++) {//我比较喜欢这种双指针的写法，即确定r枚举l 
				if(r < 0)continue; //r<0直接跳过 
				int tl = max(vec[r] - side, mini);
				int tr = min((r + 1 < len) ? vec[r + 1] - side : maxi + 1, maxi + 1) - 1;
				//如果r+1不存在，那么把上界设为maxi+1（因为后面有一个-1所以不能设为maxi）
				//此时正方形下边界的范围为[tl,tr] 
				while(l < len && vec[l] < tl)l++;//首先提出vec[l]在下边界以下的情况 
				if((vec[r] < mini + side && vec[r + 1] > mini + side) || vec[r] >= mini + side)ans++;
				//细节：此时r增加了1，不管l能不能移动，它都是一种新的情况，需要统计答案
				//当然其中也有不合法的答案，比如说vec[r]在下边界一下，但是上边界根本不可能移动到mini+side以上
				//这种情况就是ver[r+1]正好等于mini+side
				if(vec[r] - vec[l] == side)res++; //去重 
				while(l + 1 < len && vec[l] < tr) {ans++; l++; if(vec[r] - vec[l] == side)res++;}//统计答案+去重 
			}
		}
	}
	return ;
}
int main() {
	n = read(); ans = n + 1; 
	for(int i = 1; i <= n; i++) {int x = read(), y = read(); a[i] = Node(x, y);}
	solve(); 
	for(int i = 1; i <= n; i++)swap(a[i].x, a[i].y);
	solve();
	printf("%d", ans - res / 2);
	return 0;
}