Tamflexの貯蔵庫

やる気のない備忘録

codingame - Network Cabling

x軸またはy軸に平行なメインケーブルから各家庭に枝を伸ばせば良い.
中央値は絶対偏差の和を最小にすることが知られているので, メインケーブルのy座標/x座標は中央値を用いると良さそう.
証明はこちらなど↓

連続関数に関してはこちら↓
http://web.uvic.ca/~dgiles/blog/median2.pdf

さてメインケーブルのとり方について

  1. x軸に平行にしy座標の中央値にする
  2. y軸に平行にしx座標の中央値にする

の二通りの方法があるが調べてみると両者のケーブルの長さの総延長は一致することがわかる.これの証明はまた考えたい.

#define LLINF 1LL<<60

int median(vector<ll> v)
{
  int n = v.size();
  sort(v.begin(),v.end());
  return v[n/2];
}

int main()
{
  int n; cin >> n;
  vector<ll> xs(n), ys(n);
  pair<ll,ll> mx(LLINF,-LLINF);
  REP(i,n)
  {
    cin >> xs[i] >> ys[i];
    mx.first = min(xs[i],mx.first);
    mx.second = max(xs[i],mx.second);
  }
  ll a = mx.second-mx.first, m = median(ys);
  REP(i,n) a += abs(ys[i]-m);
  cout << a << endl;
  return 0;
}