ARC065 E - へんなコンパス

解法

とりあえずマンハッタン距離の有名なテクニックである,45度回転みたいなことをする.
すると,a と b の距離は D = max(|x[a] - x[b]|, |y[a] - y[b]|) となり,以降コンパスで点の位置が変わっても,この D は不変である.

あとは,今見ている点の1つを定めて,もう一方の候補がいくつあるかを探索する.
今見ている点が (x, y) なら,その点を中心にした辺の長さが 2 * D の正方形上の点を探せば良い.
これは座標(vector で持っておく)を予めソートしておいて,そのうえで4つの辺それぞれについて二分探索すると求めることができる.
今見ている点について候補の数が分かったら,もう一方の点に遷移して同じことをやる.
遷移先の探索は,set の上で行う.
一度定めた点については2度探索しないように,探索済みフラグを管理しておく.
set からも,一度探索した点は erase する.

一度探索した点は set から取り除かれていくし,探索する区間は二分探索で求めることができるので,結局計算量は O(NlogN) になる.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
 
 
vector<ll> x, y;
vector<pair<ll, ll>> ps1, ps2;
set<pair<ll, ll>> s1, s2;
map<pair<ll, ll>, int> idx;
vector<bool> vis;
 
ll calc(int i, int type, pair<ll, ll> l, pair<ll, ll> r, queue<int>& que) {
    ll res = 0;
    auto& ps = (type == 0 ? ps1 : ps2);
    auto& t1 = (type == 0 ? s1 : s2);
    auto& t2 = (type == 1 ? s2 : s1);
    res += upper_bound(ps.begin(), ps.end(), r) - lower_bound(ps.begin(), ps.end(), l);
    auto first = t1.lower_bound(l), last = t1.upper_bound(r);
    vector<pair<ll, ll>> remove_p;
    for(auto it = first; it != last; ++it) {
        auto rev_p = make_pair(it->second, it->first);
        int id = (type == 0 ? idx[*it] : idx[rev_p]);
        if(!vis[id]) {
            vis[id] = true;
            remove_p.emplace_back(it->second, it->first);
            que.push(id);
        }
    }
    t1.erase(first, last);
    for(auto& p : remove_p) {
        t2.erase(p);
    }
 
    return res;
}
 
int main() {
    int N, a, b;
    cin >> N >> a >> b;
    a--; b--;
    x.resize(N), y.resize(N);
    ps1.resize(N), ps2.resize(N);
    vis.resize(N);
    for(int i = 0; i < N; ++i) {
        cin >> x[i] >> y[i];
        ll xx = x[i] - y[i];
        ll yy = x[i] + y[i];
        x[i] = xx;
        y[i] = yy;
        ps1[i] = make_pair(xx, yy);
        ps2[i] = make_pair(yy, xx);
        s1.insert(ps1[i]);
        s2.insert(ps2[i]);
        idx[make_pair(xx, yy)] = i;
    }
    sort(ps1.begin(), ps1.end());
    sort(ps2.begin(), ps2.end());
 
    ll const D = max(abs(x[a] - x[b]), abs(y[a] - y[b]));
    vis[a] = true;
    s1.erase(make_pair(x[a], y[a]));
    s2.erase(make_pair(x[a], y[a]));
    queue<int> que;
    que.push(a);
    ll res = 0;
    while(!que.empty()) {
        auto p = que.front();
        que.pop();
        ll cur_x = x[p], cur_y = y[p];
        ll corner = idx.count(make_pair(cur_x + D, cur_y + D));
        corner += idx.count(make_pair(cur_x + D, cur_y - D));
        corner += idx.count(make_pair(cur_x - D, cur_y + D));
        corner += idx.count(make_pair(cur_x - D, cur_y - D));
 
        auto upper_left = make_pair(cur_x - D, cur_y + D);
        auto upper_right = make_pair(cur_x + D, cur_y + D);
        auto lower_left = make_pair(cur_x - D, cur_y - D);
        auto lower_right = make_pair(cur_x + D, cur_y - D);
 
        res += calc(p, 0, lower_right, upper_right, que); // right side
        res += calc(p, 0, lower_left, upper_left, que);   // left side
 
        swap(upper_left.first, upper_left.second);
        swap(upper_right.first, upper_right.second);
        swap(lower_left.first, lower_left.second);
        swap(lower_right.first, lower_right.second);
 
        res += calc(p, 1, upper_left, upper_right, que);  // upper side
        res += calc(p, 1, lower_left, lower_right, que);  // lower side
 
        res -= corner;
    }
 
    cout << res / 2 << endl;
}

感想

BFSじゃなくてDFSのほうが無駄な処理がなくていいかもしれない.
set の erase が意外と無視できなくて,erase(first, last) をやめると定数倍で死にます.
set を使わない実装もあったので,書けるならそっちのほうが良さそう.僕はかけなかった.