ARC065 E - へんなコンパス
解法
とりあえずマンハッタン距離の有名なテクニックである,45度回転みたいなことをする.
すると,a と b の距離は D = max(|x[a] - x[b]|, |y[a] - y[b]|) となり,以降コンパスで点の位置が変わっても,この D は不変である.
あとは,今見ている点の1つを定めて,もう一方の候補がいくつあるかを探索する.
今見ている点が (x, y) なら,その点を中心にした辺の長さが 2 * D の正方形上の点を探せば良い.
これは座標(vector
今見ている点について候補の数が分かったら,もう一方の点に遷移して同じことをやる.
遷移先の探索は,set
一度定めた点については2度探索しないように,探索済みフラグを管理しておく.
set
一度探索した点は 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 を使わない実装もあったので,書けるならそっちのほうが良さそう.僕はかけなかった.