AOJ 0563: Walking Santa

問題

を満たすx, y, v を求める

解法

maxの項が存在しない場合は、各軸で考えて、中央値を選べば良く、Nが偶数のときは、中央の2つの値の間の値であればどれでもよい。Nが奇数のときは一意に定まる。
maxの項が存在する場合の解は、上の問題の解のどれかであり、端点だけ調べれば良い。
計算量は、O(NlogN) (O(N)にもできる)

コード

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int main(){
	ll h, w, n;
	scanf("%ld%ld%ld",&h,&w,&n);
	vector<ll> x(n),y(n);
	vector<P> p(n);
	for(int i = 0; i < n; i++){
		scanf("%ld%ld",&x[i],&y[i]);
		p[i] = P(x[i], y[i]);
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	ll rx, ry, rv = -1;
	for(int i = 0; i < 4; i++){
		ll ax = x[(n-1+i/2)/2], ay = y[(n-1+i%2)/2];
		ll mx = 0;
		for(int j = 0; j < n; j++)
			mx = max(mx, abs(ax-p[j].first)+abs(ay-p[j].second));
		if(rv<mx){
			rx = ax;
			ry = ay;
			rv = mx;
		}
	}
	ll res = -rv;
	for(int i = 0; i < n; i++)
		res += 2*(abs(rx-x[i])+abs(ry-y[i]));
	printf("%ld\n%ld %ld\n", res, rx, ry);
	return 0;
}