SRM 325 Div1 Medium TournamentPlan

問題

グリッド上の町にN人の競技者がいて、i番目の競技者が(street[i], avenue[i])にいる。競技者は道路の交差した位置で出会うと競技を行って勝敗を決める。この競技で総当り戦を行うとき、全競技者の総移動量を最小化せよ。

やりかた

どこかの交差点に全員が集まれば良いというのはなんとなく想像がつく。そしてなるべく真ん中の方に集まれば最小になるので、X軸方向に見た時に真ん中に属している一人（もしくは二人）のX座標と、Y軸方向に見た時に真ん中に属している一人（もしくは二人）のY座標の交点に対して集まればいい。

以下ソース。全競技者の初期位置のXとYに対して地点の候補としているのであまりかっこよくないコード。

class TournamentPlan {
public:
  int getTravelDistance(vector <int> street, vector <int> avenue){
    int N = street.size();
    vector<pair<int, int> > p;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++) 
	p.push_back(make_pair(street[i], avenue[j])); 
    
    int M = p.size();
    int ans = INF;
    for(int i = 0; i < M; i++){
      int tmp = 0;
      for(int j = 0; j < N; j++) 
	tmp += abs(street[j] - p[i].first) + abs(avenue[j] - p[i].second);
      ans = min(ans, tmp);
    }
	
    return ans;
  }
};