Підрахунок сусідів#11861

Підрахунок сусідів (Розбір)

Автор проблеми:	TheSensei
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	Hasan Saleh (MathModel)

Розв'язок

Зверніть увагу, що $d$ мале, набір точок, які вважаються "сусідами" деякої точки $(x, y)$ — це всі точки, які мають манхеттенську відстань не більше $d$ , тому ми можемо перебрати всі точки $(x - a, y - b)$ (x-a,y-b), де $(- d \leq a, b \leq d)$ (-d \le a,b \le d) і підрахувати такі точки, використовуючи структуру даних map. Зверніть увагу, що не всі точки будуть працювати з таким перебором, тому потрібно перевірити, чи вони задовольняють умову манхеттенської відстані, що дає загальну складність $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++

Складність $O (n \cdot d^{2})$ \mathcal{O}(n \cdot d^2)