Qonşuları Saymaq#11861

Qonşuları Saymaq (Həll təhlili)

Problem Müəllifi:	TheSensei
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Qeyd edin ki, $d$ kiçikdir, $(x, y)$ nöqtəsinə "yaxın" sayılan nöqtələrin dəsti, Manhattan məsafəsi ən çox $d$ olan bütün nöqtələrdir, buna görə $(x - a, y - b)$ (x-a,y-b) nöqtələrinin bütün nöqtələrini qabarıq şəkildə yoxlaya bilərik, burada $(- d \leq a, b \leq d)$ (-d \le a,b \le d) və belə nöqtələri bir xəritə məlumat strukturu istifadə edərək saymaq olar. Qeyd edin ki, bütün nöqtələr belə iterasiya ilə işləməyəcək, buna görə də onların Manhattan məsafəsi şərtini ödəyib-ödəmədiyini yoxlamalısınız. Bu, $O (n \cdot d^{2})$ \mathcal{O}(n \cdot d^2) ümumi mürəkkəbliyini verir.

//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++

Mürəkkəblik $O (n \cdot d^{2})$ \mathcal{O}(n \cdot d^2)