考えやすい感じの問題なのでちょっと好き。

D - バス停

問題

二分する。軸に並行にバス停を並べ半分に分割することを繰り返す。

適当な$y = m$を固定し、全てのバス停$(x_i,y_i)$に関し、その影となる$(x_i,m)$に新たなバス停を設置する。すると直線$y = m$を間に挟むバス停同士、つまりバス停$i$と$j$が$y_i \le m \le y_j$あるいは$y_j \le m \le y_i$ならば、それらの間は最短距離で移動できる。 この分割を再帰的にやればよい。

特に、入力$N \le 1000$で、出力$M \le 10000 - N$。 $1000$から初めて再帰的に$2$で割っていくと$1000,500,250,125,62,31,15,7,3,1$となり、$9$回目で$1$になる。 設置するバス停は$1000 + (500 + 500) + (250 + 250 + 250 + 250) + \dots + (1 + 1 + \dots + 1) = 1000 \cdot 9$で抑えられるので、これで十分である。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
struct point_t { int y, x; };
bool operator == (point_t a, point_t b) { return make_pair(a.y, a.x) == make_pair(b.y, b.x); }
bool operator  < (point_t a, point_t b) { return make_pair(a.y, a.x)  < make_pair(b.y, b.x); }
const int W = 1001;
int main() {
    int n; cin >> n;
    set<point_t> ps;
    vector<set<int> > ys(W);
    repeat (i,n) {
        int y, x; cin >> x >> y;
        ps.insert((point_t) { y, x });
        ys[y].insert(x);
    }
    vector<point_t> qs;
    function<void (int, int, int)> split = [&](int l, int r, int n) {
        if (n <= 1) return;
        int acc = 0, nacc;
        int m; for (m = l; m < r; ++ m) {
            nacc = acc + ys[m].size();
            if (n/2 <= nacc) break;
            acc = nacc;
        }
        repeat_from (y, l, r) if (y != m) {
            for (int x : ys[y]) {
                qs.push_back((point_t) { m, x });
            }
        }
        split(l, m, acc);
        split(m+1, r, n - nacc);
    };
    split(0, W, n);
    qs.erase(remove_if(qs.begin(), qs.end(), [&](point_t p) { return ps.count(p); }), qs.end());
    sort(qs.begin(), qs.end());
    qs.erase(unique(qs.begin(), qs.end()), qs.end());
    cout << qs.size() << endl;
    for (point_t q : qs) cout << q.x << ' ' << q.y << endl;
    return 0;
}