题目大意

二维平面上有 $n$ 个整点，每个整点的坐标为 $(x_i,y_i)$ ，若两个点 $i,j$ 满足 $|x_i-x_j|+|y_i-y_j|\le R$ ，则在这两个点之间连一条边。求联通块的数量。

$1\le n\le 100000,0\le r,x_i,y_i\le 10^9$

解题思路

如果暴力建边，当所有节点都满足互相连边的条件，即所有节点挤在一起时，边的数量是 $O(n^2)$ 的，显然无法忍受。这时我们需要考虑一些优化建图的方法。

我们将一个点的影响范围画出来，如下矩阵：

0001000
0011100
0111110
1111111
0111110
0011100
0001000

$R=3$ 时的情况

我们发现每个点的影响范围都是一个与坐标轴夹角为 $45\degree$ 的直线围成的正方形，即由斜率 $k=1$ 和 $k=-1$ 的直线围成的正方形。

如果每个点的影响范围是一个与坐标轴平行的矩形，我们可以用扫描线法维护优化连边。

因为此题的影响范围是斜着的正方形，所以我们就斜着扫描线。

我们将所有点按照 $x_i+y_i$ 的值从小到大进行排序，进行扫描线。扫描线为一条斜率为 $-1$ 的直线，其维护的是对当前答案有贡献的点的位置。在本人的代码实现中，用 set 维护扫描线。

一个点的坐标为 $(x_i,y_i)$ ，其对应值 $x_i-y_i$ 会在扫描线 $x_i+y_i$ 时加入扫描线，在扫描线 $x_i+y_i+R$ 时退出扫描线。

我们将每个斜率为 $1$ 上的整点进行一个对应关系，令其对应值为 $p_i=x_i-y_i$ ，保证所有这些点的对应值相等。

一个节点 $y$ 能与当前节点 $x$ 相连，当且仅当它们的对应值的差 $|p_x-p_y|\le R$ 。这时可以在并查集上 merge 两个节点。

然而，这样的复杂度是和边数同阶的。给出一个结论：直接将节点 $x$ 与可连的向左向右最接近的点连边，因为 $x$ 其它可连的点在之前肯定都在扫描线上，而都连上了，这样可以控制边数是 $O(n)$ 的。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=100010;
int n,r,f[maxn],ans,cur;
int findp(int x){return f[x]?f[x]=findp(f[x]):x;}
void merge(int x,int y)
{
	int u=findp(x),v=findp(y);
	if(u!=v)f[u]=v,ans--;
}
struct node
{
	int x,y;
	bool operator<(node a)const{if(x+y!=a.x+a.y)return x+y<a.x+a.y;return x<a.x;}
}s[maxn];
map<int,int>st;
int main()
{
	scanf("%d%d",&n,&r);ans=n;
	for(int i=1;i<=n;i++)scanf("%d%d",&s[i].x,&s[i].y);
	sort(s+1,s+n+1);
	cur=1;
	st[2e9+1]=-1;st[-(2e9+1)]=-1;
	for(int i=1;i<=n;i++)
	{
		for(;cur<=n&&s[cur].x+s[cur].y+r<s[i].x+s[i].y;cur++)
		if(st[s[cur].x-s[cur].y]==cur)st.erase(s[cur].x-s[cur].y);
		map<int,int>::iterator it=st.lower_bound(s[i].x-s[i].y);
		if(it->first-(s[i].x-s[i].y)<=r)if(it->second)merge(i,it->second);
		it--;
		if(s[i].x-s[i].y-it->first<=r)if(it->second)merge(i,it->second);
		st[s[i].x-s[i].y]=i;
	}
	printf("%d\n",ans);
	return 0;
}