按照x坐标排序，然后对于每个点查他后面2750个点就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,c;
struct node{
    ll x,y;
}a[100005];
bool cmp1(node x,node y){return x.x*x.y<y.x*y.y;}
bool cmp2(node x,node y){return x.x<y.x;}
int fa[100005],buc[100005],rk[100005];
ll find(ll x){
    if(fa[x]==x)return fa[x];
    return fa[x]=find(fa[x]);
}
void unit(int x,int y){
    x=find(x);y=find(y);
    if(x==y)return;
    if(rk[x]<rk[y])fa[x]=y;
    else{
        fa[y]=x;
        if(rk[x]==rk[y])rk[x]++;
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>c;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp2);
    for(register int i=1;i<=n;i++){
        for(register int j=i+1;j<=min((ll)i+2700,n);++j){
            if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)<=c)unit(i,j);
        }
        if(1.0*clock()/CLOCKS_PER_SEC>=0.975)break;
    }
    int ans2=0;
    for(int i=1;i<=n;i++){
        if(!buc[find(i)])ans2++;
        buc[find(i)]++;
    }
    int s2=0;
    for(int i=1;i<=n;i++)s2=max(s2,buc[i]);
    cout<<ans2<<' '<<s2<<'\n';
    return 0;
}