给定平面的n个点（n<=1e5），所有坐标的绝对值在50000以内，现在问你有多少对点之间的距离不小于d。这里距离描述为两点的曼哈顿距离，即dist=|xi-xj|+|yi-yj|。
思路如果将平面上小于等于d的曼哈顿距离画出来，会是一个菱形
贪玩的冬日距离：平面上两个点(x1,y1)(x2,y2)的贪玩的冬日距离为max(∣x1−x2∣,∣y1−y2∣),其中∣x∣为x的绝对值
将曼哈顿距离转换为贪玩的冬日距离后，我们发现贪玩的冬日距离固定的点呈正方形
这样我们就可以先将数据离线，按照yy的大小对点进行排序，然后用树状数组维护长度为dd的正方形区域内点的个数即可，这部分代码相对就比较模板了
#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn=1e6+10;int n,d,fk;const int fix=5e5+10;struct Point{ int x,y; bool operator < (const Point &rhs)const{ return x<rhs.x; }}node[maxn];int lowbit(int x){ return x&-x;}int c[maxn];void add(int x,int v){ while(x<maxn){ c[x]+=v; x+=lowbit(x); }}int Sum(int x){ int res=0; while(x>0){ res+=c[x]; x-=lowbit(x); } return res;}signed main(){ scanf("%lld%lld%lld",&n,&d,&fk); d--; for(int i=1;i<=n;i++){ int x,y; scanf("%lld%lld",&x,&y); //转化为贪玩的冬日坐标 node[i].x=x+y; node[i].y=x-y+fix; } sort(node+1,node+n+1); int ans=0; for(int i=1,j=1;i<=n;i++){ while(j<i&&node[i].x-node[j].x>d){ add(node[j].y,-1); j++; } ans+=Sum(node[i].y+d)-Sum(node[i].y-d-1); add(node[i].y,1); } ans=n*(n-1)/2-ans; printf("%lldn",ans); return 0;}