PKU 3269 Building A New Barn

要約 : 牛が二次元にn頭生えているので、全ての牛からのマンハッタン距離の和が最短となるような点は何個あるか??ただし牛がいるところは除く。

どっかのJOIで見たサンタもどき。中央値を適正に考えると解ける。
隣接する点に牛がいないという制約のおかげで楽。


nが奇数の時は基本1個だがそこに牛がいたら周囲の4点を調べる。
nが偶数の時はx, y座標の中央値がなす長方形から牛がいる点の数をひく。

何を血迷ったのか2次元BITを1回書いてMLEした

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define fi first
#define se second
#define mp make_pair

typedef pair<int, int> P;
typedef long long Int;

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int n;
int x[20010], y[20010];
P pos[10010];
Int dist, num;

/*
struct BIT{
    int tree[10010][10010];
    BIT(){ memset(tree, 0, sizeof(tree)); }

    void add(int x , int y , int val){
	int ny;
	while (x <= 10000){
	    ny = y;
	    while (ny <= 10000){
		tree[x][ny] += val;
		ny += (ny & -ny); 
	    }
	    x += (x & -x); 
	}
    }

    int sum(int x, int y){
	int s = 0, ny;
	while(x){
	    ny = y;
	    while(ny > 0){
		s += tree[x][ny]; 
		ny -= (ny & -ny);
	    }
	    x -= (x & -x);
	}
    }

}b;
*/

int main(){
    scanf("%d", &n);
    rep(i, n){
	scanf("%d %d", &pos[i].fi, &pos[i].se);
	pos[i].fi += 10000; pos[i].se += 10000;
	x[i] = pos[i].fi; y[i] = pos[i].se;
    }
    sort(pos, pos + n); sort(x, x + n); sort(y, y + n);
    if(n & 1){
	int nx, ny;
	nx = x[(n - 1) / 2], ny = y[(n - 1) / 2];
	if(binary_search(pos, pos + n, mp(nx, ny))){
	    Int d[4];
	    rep(t, 4){
		d[t] = 0;
		int px = nx + dx[t], py = ny + dy[t];
		rep(i, n){
		    d[t] += abs(x[i] - px) + abs(y[i] - py);
		}
	    }
	    dist = *min_element(d, d + 4);
	    rep(i, 4) if(d[i] == dist) num++;
	}else{
	    num = 1;
	    rep(i, n){
		dist += abs(x[i] - nx) + abs(y[i] - ny);
	    }
	}
    }else{
	int mx, Mx, my, My;
	mx = x[n / 2 - 1], Mx = x[n / 2], my = y[n / 2 - 1], My = y[n / 2];
	num = (Int)(Mx - mx + 1) * (Int)(My - my + 1);
	rep(i, n){
	    if(pos[i].fi >= mx && pos[i].fi <= Mx && pos[i].se >= my && pos[i].se <= My) --num;
	    dist += abs(x[i] - mx) + abs(y[i] - my);
	}
	assert(num > 0);
    }
    printf("%lld %lld\n", dist, num);
    return 0;
}