Compter les Voisins#11861

Compter les Voisins (Corrigé)

Auteur du Problème :	TheSensei
Préparé par :	Hasan Saleh (MathModel)
Édité par :	Hasan Saleh (MathModel)

Solution

Remarquez que $d$ est petit, l'ensemble des points considérés comme "proches" d'un point $(x, y)$ est tous les points ayant une distance de Manhattan d'au plus $d$ , puis nous pouvons forcer tous les points de $(x - a, y - b)$ (x-a,y-b) où $(- d \leq a, b \leq d)$ (-d \le a,b \le d) et compter ces points en utilisant une structure de données de carte, Notez que tous les points ne fonctionneront pas avec cette itération donc vous devez vérifier s'ils satisfont la condition de distance de Manhattan, ce qui donne une complexité totale 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++

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