Contando Vecinos#11861

Contando Vecinos (Editorial)

Autor del Problema:	TheSensei
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución

Observa que $d$ es pequeño. El conjunto de puntos que se consideran "cercanos" a algún punto $(x, y)$ son todos los puntos que tienen una distancia de Manhattan de como máximo $d$ , por lo que podemos hacer una fuerza bruta en todos los puntos de $(x - a, y - b)$ (x-a,y-b) donde $(- d \leq a, b \leq d)$ (-d \le a,b \le d) y contar tales puntos utilizando una estructura de datos de mapa. Ten en cuenta que no todos los puntos funcionarán con tal iteración, así que debes verificar si satisfacen la condición de distancia de Manhattan. Esto da como resultado una complejidad total de $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++

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