提出 #28441485

---

ソースコード 拡げる

/*
 * Author: nskybytskyi
 * Time:   2022-01-08 14:00:00
 */

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n, k;
  cin >> n >> k;

  vector<pair<int, int>> xy(n);
  for (auto& [x, y] : xy) {
    cin >> x >> y;
  }

  map<pair<int, int>, vector<int>> groups;

  for (int i = 0; i < n; ++i) {
    auto [x, y] = xy[i];
    groups[make_pair(x / k, y / k)].push_back(i);
  }

  // We'll check all pairs of points in adjacent groups
  // One may think that this number is quadratic
  // But it turns out that "almost" every such pair works
  // I.e. the number of pairs we chek is O(M)

  set<pair<int, int>> close;

  auto adjacent_groups = [&] (pair<int, int> group) -> vector<pair<int, int>> {
    auto [x, y] = group;
    vector<pair<int, int>> groups;
    for (int x_difference = -1; x_difference <= 1; ++x_difference) {
      for (int y_difference = -1; y_difference <= 1; ++y_difference) {
        groups.emplace_back(x + x_difference, y + y_difference);
      }
    }
    return groups;
  };

  auto distance_squared = [&] (int i, int j) -> int64_t {
    return (xy[i].first - xy[j].first) * 1ll * (xy[i].first - xy[j].first) \
      +  (xy[i].second - xy[j].second) * 1ll * (xy[i].second - xy[j].second);
  };

  for (const auto& [group, points] : groups) {
    for (auto adjacent_group : adjacent_groups(group)) {
      if (groups.count(adjacent_group)) {
        for (auto point : points) {
          for (auto adjacent_point : groups[adjacent_group]) {
            if (distance_squared(point, adjacent_point) <= k * 1ll * k) {
              if (point < adjacent_point) {
                close.emplace(point, adjacent_point);
              }
            }
          }
        }
      }
    }
  }

  cout << close.size() << "\n";
  for (auto [i, j] : close) {
    cout << i + 1 << " " << j + 1 << "\n";
  }

  return 0;
}

提出情報

ジャッジ結果