Language: C++

#include <cassert>
#include <unordered_map>
#include <queue>
#include <set>
#include <vector>
using namespace std;

int L1(int a, int b, int c, int d) {
    return abs(a - c) + abs(b - d);
}

int main() {
    int N, a, b; cin >> N >> a >> b;
    int x[N], y[N];
    struct Point {
        int x, y;
        int idx;
        bool operator<(const Point& other) const {
            return x < other.x;
        };
        Point(int x, int y, int i) : x(x), y(y), idx(i) {};
    };
    unordered_map<int, set<Point> > unvisited[2];
    unordered_map<int, vector<Point> > all[2];
    auto get_point = [&](int i) { return Point(x[i], y[i], i); };
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        Point p = get_point(i);
        unvisited[0][x[i] + y[i]].insert(p);
        unvisited[1][x[i] - y[i]].insert(p);
        all[0][x[i] + y[i]].push_back(p);
        all[1][x[i] - y[i]].push_back(p);
    }
    for (auto &x : all) for (auto& [k, v] : x) sort(v.begin(), v.end());
    const int d = L1(x[a-1], y[a-1], x[b-1], y[b-1]);
    queue<int> q;
    auto visit = [&](int i) {
        Point p = get_point(i);
        unvisited[0][x[i] + y[i]].erase(p);
        unvisited[1][x[i] - y[i]].erase(p);
    };
    q.push(a-1);
    visit(a-1);
    long long ans = 0;
    auto get_count = [](vector<Point> &v, int lb, int ub) {
        auto l = partition_point(v.begin(), v.end(), [lb](Point q) { return q.x < lb; }),
        r = partition_point(v.begin(), v.end(), [ub](Point q) { return q.x <= ub; });
        return abs(distance(l, r));
    };

    while (!q.empty()) {
        int i = q.front();
        q.pop();
        Point p = Point(x[i], y[i], i);
        // cerr << x[i] << " " << y[i] << endl;

        if (auto it = all[0].find(x[i] + y[i] + d); it != all[0].end())
            ans += get_count(it->second, p.x+1, p.x+d);
        if (auto it = all[1].find(x[i] - y[i] - d); it != all[1].end())
            ans += get_count(it->second, p.x-d+1, p.x);
        if (auto it = all[0].find(x[i] + y[i] - d); it != all[0].end())
            ans += get_count(it->second, p.x-d, p.x-1);
        if (auto it = all[1].find(x[i] - y[i] + d); it != all[1].end())
            ans += get_count(it->second, p.x, p.x+d-1);

        // cerr << ans << endl;

        set<int> visited;
        auto record_visit = [&](set<Point> &s, int lb, int ub) {
            for (auto it = s.lower_bound(Point(lb, 0, 0)); it != s.end() && it->x <= ub; it++)
                visited.insert(it->idx);
        };
        if (auto it = unvisited[0].find(x[i] + y[i] + d); it != unvisited[0].end())
            record_visit(it->second, p.x+1, p.x+d);
        if (auto it = unvisited[1].find(x[i] - y[i] - d); it != unvisited[1].end())
            record_visit(it->second, p.x-d+1, p.x);
        if (auto it = unvisited[0].find(x[i] + y[i] - d); it != unvisited[0].end())
            record_visit(it->second, p.x-d, p.x-1);
        if (auto it = unvisited[1].find(x[i] - y[i] + d); it != unvisited[1].end())
            record_visit(it->second, p.x, p.x+d-1);

        for (int j : visited) { visit(j); q.push(j); }
        // for (int j : visited) cerr << x[i] << " "<< y[i] << " -> " << x[j] << " " << y[j] << endl;
    }
    cout << ans / 2 << endl;

    //check
    // q.push(a-1);
    // vector<bool> used(N, false);
    // used[a-1] = true;
    // long long expect = 0;
    // while (!q.empty()) {
    //     int i = q.front();
    //     q.pop();
    //     for (int j = 0; j < N; j++) {
    //         if (L1(x[i], y[i], x[j], y[j]) == d) {
    //             expect++;
    //             if (!used[j]) {
    //                 used[j] = true;
    //                 q.push(j);
    //             }
    //         }
    //     }
    // }
    // assert(ans == expect);
}


Compiler output:
a.cc: In function 'int L1(int, int, int, int)':
a.cc:9:12: error: 'abs' was not declared in this scope
    9 |     return abs(a - c) + abs(b - d);
      |            ^~~
a.cc: In function 'int main()':
a.cc:13:18: error: 'cin' was not declared in this scope
   13 |     int N, a, b; cin >> N >> a >> b;
      |                  ^~~
a.cc:5:1: note: 'std::cin' is defined in header '<iostream>'; this is probably fixable by adding '#include <iostream>'
    4 | #include <set>
  +++ |+#include <iostream>
    5 | #include <vector>
a.cc:34:48: error: 'sort' was not declared in this scope; did you mean 'short'?
   34 |     for (auto &x : all) for (auto& [k, v] : x) sort(v.begin(), v.end());
      |                                                ^~~~
      |                                                short
a.cc: In lambda function:
a.cc:46:18: error: 'partition_point' was not declared in this scope
   46 |         auto l = partition_point(v.begin(), v.end(), [lb](Point q) { return q.x < lb; }),
      |                  ^~~~~~~~~~~~~~~
a.cc:47:84: error: expected ',' or ';' before ')' token
   47 |         r = partition_point(v.begin(), v.end(), [ub](Point q) { return q.x <= ub; });
      |                                                                                    ^
a.cc:48:32: error: 'r' was not declared in this scope
   48 |         return abs(distance(l, r));
      |                                ^
a.cc:48:16: error: 'abs' was not declared in this scope; did you mean 'ans'?
   48 |         return abs(distance(l, r));
      |                ^~~
      |                ans
a.cc: In function 'int main()':
a.cc:85:5: error: 'cout' was not declared in this scope
   85 |     cout << ans / 2 << endl;
      |     ^~~~
a.cc:85:5: note: 'std::cout' is defined in header '<iostream>'; this is probably fixable by adding '#include <iostream>'
a.cc:85:24: error: 'endl' was not declared in this scope
   85 |     cout << ans / 2 << endl;
      |                        ^~~~
a.cc:5:1: note: 'std::endl' is defined in header '<ostream>'; this is probably fixable by adding '#include <ostream>'
    4 | #include <set>
  +++ |+#include <ostream>
    5 | #include <vector>