dadasd

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;

#include <unordered_map>
#include <vector>
#include <cmath>
#include <functional> // For custom hash function
using namespace std;

// Custom hash function for pair<int, int>
struct pair_hash {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ h2;  // Combine the two hashes
    }
};

// Helper function to compute the bucket key based on center coordinates
pair<int, int> getBucket(int x, int y) {
    return {x / 2, y / 2};  // Each bucket represents a 2x2 area
}

int countCollidingPairs(vector<vector<int>>& centers) {
    unordered_map<pair<int, int>, vector<pair<int, int>>, pair_hash> buckets;
    int count = 0;

    for (const auto& center : centers) {
        int x = center[0], y = center[1];
        auto bucket = getBucket(x, y);

        // Check the current bucket and all neighboring buckets
        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                auto neighborBucket = make_pair(bucket.first + dx, bucket.second + dy);
                if (buckets.find(neighborBucket) != buckets.end()) {
                    for (const auto& other : buckets[neighborBucket]) {
                        // Check if the distance between the centers is <= 2
                        if (abs(other.first - x) <= 2 && abs(other.second - y) <= 2) {
                            ++count;
                        }
                    }
                }
            }
        }

        // Add the current object to its bucket
        buckets[bucket].emplace_back(x, y);
    }

    return count;
}

int main() {
    vector<vector<int>> centers = {
        {1, 1}, {100000, 100000}, {99998, 99998},{100000,99996}
    };
    int result = countCollidingPairs(centers);
    cout << "Number of colliding pairs: " << result << endl;

    return 0;
}