寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #D - 歩くサンタクロース (Walking Santa)

第10回日本情報オリンピック 本選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#D - 歩くサンタクロース (Walking Santa)

https://www.ioi-jp.org/joi/2010/2011-ho-tasks_data/2011-ho.pdf#page=9

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#D - 歩くサンタクロース (Walking Santa)
https://www.ioi-jp.org/joi/2010/2011-ho-tasks_data/2011-ho.pdf#page=9
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
  ll h,w,n;
  cin>>h>>w>>n;
  vector<ll> x(n),y(n);
  for(ll i=0;i<n;i++){
    cin>>x[i]>>y[i];
  }
  vector<ll> X=x,Y=y;
  sort(X.begin(),X.end());
  sort(Y.begin(),Y.end());
  vector<ll> a,b;
  if(n%2==0){
    a={X[n/2-1],X[n/2]};
    b={Y[n/2-1],Y[n/2]};
  }else{
    a={X[n/2]};
    b={Y[n/2]};
  }
  ll ans=1e18;
  ll ax=-1,ay=-1;
  for(ll i : a){
    for(ll j : b){
      ll cnt=0;
      ll mx=0;
      for(ll k=0;k<n;k++){
        cnt+=abs(i-x[k])+abs(j-y[k]);
        mx=max(mx,(ll)abs(i-x[k])+abs(j-y[k]));
      }
      if(ans>cnt*2-mx){
        ans=cnt*2-mx;
        ax=i;
        ay=j;
      }
    }
  }
  cout<<ans<<endl;
  cout<<ax<<" "<<ay<<endl;
  return 0;
}