第10回日本情報オリンピック 本選 「歩くサンタクロース」 AOJ0563 (Walking Santa)

このブログがものすごくわかりやすいです。

JOI2011本戦 第四問「歩くサンタクロース」 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
const int Y = 100003;
int w,h,n;
int x[Y],y[Y],sx[Y],sy[Y],ansx,ansy;
ll ans = 1000000000000000,sumd,maxd;
int main(){
	scanf("%d%d%d",&w,&h,&n);
	for(int i = 0;i < n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		x[i] = a,y[i] = b,sx[i] = a,sy[i] = b;
	}
	sort(x,x + n);
	sort(y,y + n);
	for(int i = 1;i >= 0;i--){
		for(int j = 1;j >= 0;j--){
			ll a = x[(n-i)/2];
			ll b = y[(n-j)/2];
			sumd = 0,maxd = 0;
			for(int k = 0;k < n;k++){
				ll d = abs(a-sx[k]) + abs(b-sy[k]);
				sumd += d*2;
				maxd = max(maxd,d);
			}
			if(ans > sumd - maxd){
				ans = sumd - maxd;
				ansx = a;
				ansy = b;
			}
		}
	}
	printf("%lld\n%d %d\n",ans,ansx,ansy);
	return 0;
}