AOJ 0563 歩くサンタクロース

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0563
　最近実装が軽い問題を好んでおり、よくない。
　とはいうもののこれは面白かったのでメモしておく。

概要

xy平面上に点集合S（濃度N）がある。ある点Kを決め、N個の点とのマンハッタン距離の総和 * 2(i) - KとS中の点のマンハッタン距離の最大値 が最小になるようにしろ。

解法

　まずx,yについてそれぞれ中央値をとる。これが最適になるのは定番問題だが、問題はNが偶数のときだ。
　中央二値K1, K2について、この間にある点すべてが候補になるのではないか、そしたらO(マス目)になり間に合わない、と悩んだ。
　だが結局K1 * K2の値の組み合わせ（最大４通り）を試すだけでいい。

　点が四つの場合の中央2値の範囲はこんな感じになる。
　この長方形の中の隅でない点kで、Sに含まれる点との距離が最大となるものがあったとする。このときのS内の点をnとしてnが下にくるように紙を回転させると、

　とまあこんな感じですみっこが一番遠くなるという。これで説明になってるのか？

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

using i64 = long long;
i64 calc(i64& mean, const vector<i64>& vec, vector<i64>& ma) {
    i64 res = 0LL;
    for(int i : in(vec.size())) {
        i64 t = vec[i];
        i64 plus = mean > t ? mean - t : t - mean;
        ma[i] += plus;
        res += plus << 1LL;
    }
    return res;
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    i64 w, h, n;
    cin >> w >> h >> n;
    vector<i64> xcoord(n), ycoord(n);
    for(int i : in(n))
      cin >> xcoord[i] >> ycoord[i];
    auto sortx = xcoord, sorty = ycoord;
    sort(sortx.begin(), sortx.end());
    sort(sorty.begin(), sorty.end());
    vector<i64> midId = {n / 2};
    if(~n & 1) midId.emplace_back(n / 2 - 1);
    tuple<i64, i64, i64> ans(1e18, 0LL, 0LL);
    for(auto id1 : midId) for(auto id2 : midId) {
        i64 x = sortx[id1], y = sorty[id2];
        vector<i64> ma(n, 0LL);
        i64 sum = calc(x, xcoord, ma) + calc(y, ycoord, ma);
        sum -= *max_element(ma.begin(), ma.end());
        ans = min(ans, make_tuple(sum, x, y));
    }
    i64 sum, x, y; tie(sum, x, y) = ans;
    cout << sum << '\n' << x << ' ' << y << endl;
    return 0;
}