Counting Neighbors#11861

Counting Neighbors (Editorial)

Problem Author:	TheSensei
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

Notice that $d$ is small , The set of points that are considered "near-by" some point $(x, y)$ is all points that have a Manhattan distance of at most $d$ , then we can brute force all points of $(x - a, y - b)$ (x-a,y-b) where $(- d \leq a, b \leq d)$ (-d \le a,b \le d) and count such points using a map data structure , Note that not all points will work with such iteration so you've to check if they satisfy the Manhattan distance condition , Yields a total complexity of $O (n \cdot d^{2})$ \mathcal{O}(n \cdot d^2)

//O(n^2)

#include<bits/stdc++.h>
using namespace std;
#define int long long

int ok(pair<int,int>a,pair<int,int>b,int d){
    if(abs(a.first-b.first)+abs(a.second-b.second)<=d){
        return 1; 
    }
    return 0;
}

void solve(){
    int n,d;cin>>n>>d;
    vector<pair<int,int>>p(n);
    map<pair<int,int>,int>mp;
    for(auto &i:p){
        cin>>i.first>>i.second;
        mp[{i.first,i.second}]=1;
    }
    for(int i=0;i<n;i++){
        int cur=0;  
        for(int x=p[i].first-d;x<=p[i].first+d;x++){
            for(int y=p[i].second-d;y<=p[i].second+d;y++){
                if(mp[{x,y}]){
                    if(!(x==p[i].first && y==p[i].second)){
                        if(ok({x,y},p[i],d)){
                            cur++;
                        }
                    }
                }
            }
        }
        cout<<cur<<" ";
    }
    cout<<"\n";
}

signed main(){
    int t;cin>>t;
    while(t--){
        solve();
    }
}

C++

Complexity $O (n \cdot d^{2})$ \mathcal{O}(n \cdot d^2)