読者です 読者をやめる 読者になる 読者になる

AOJ0563 Walking Santa

AIZU ONLINE JUDGE
少し考えると始点の選び方の候補が絞られることがわかる。
nが奇数の時は1箇所に決まるが、偶数の時は4通り調べる。
偶数の時に2通りしか調べなかったり、答える座標が適切でなかったりしてわ〜してた。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int n;
ll w, h, x[100000], y[100000], dx[100000], dy[100000], ans, tans[2][2], gx, gy, tx[2], ty[2];

int main(){
    scanf("%lld %lld %d", &w, &h, &n);
    for(int i = 0; i < n; i++) scanf("%lld %lld", &x[i], &y[i]);
    memcpy(dx, x, sizeof(x));
    memcpy(dy, y, sizeof(y));
    sort(x, x + n);
    sort(y, y + n);
    gx = x[n / 2];
    gy = y[n / 2];
    for(int i = 0; i < n; i++) ans += 2 * (abs(x[i] - gx) + abs(y[i] - gy));
    ll tmp = 0;
    for(int i = 0; i < n; i++){
	tmp = max(tmp, abs(gx - dx[i]) + abs(gy - dy[i]));
    }
    ans -= tmp;
    if(!(n & 1)){
	for(int i = 0; i < 2; i++){
	    tx[i] = x[n / 2 - i];
	    for(int j = 0; j < 2; j++){
		if(!(i || j)) continue;
		ty[j] = y[n / 2 - j];
		for(int p = 0; p < n; p++) tans[i][j] += 2 * (abs(x[p] - tx[i]) + abs(y[p] - ty[j]));
		tmp = 0;
		for(int p = 0; p < n; p++){
		    tmp = max(tmp, abs(tx[i] - dx[p]) + abs(ty[j] - dy[p]));
		}
		tans[i][j] -= tmp;
		if(tans[i][j] <= ans){
		    ans = tans[i][j];
		    gx = tx[i];
		    gy = ty[j];
		}
	    }
	}
    }
    printf("%lld\n%lld %lld\n", ans, gx, gy);
    return 0;
}