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; }