A - 2点間距離の最大値 ( The longest distance )

コメント歓迎です。

問題

AtCoder 版！蟻本 (初級編) - Qiita より

arc004.contest.atcoder.jp

方針

 2点間の距離を全パターン計算。
今まで計算した中での最大値を保持して、計算するたびに比較。
保持していた最大値よりも今計算した値が大きければ最大値を更新。
全パターン計算後、保持していた最大値が全パターン中の最大値となる。

２点間の距離の計算はピタゴラスの定理より下式ですね。

 

コード

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main(){

  int N;
  vector<int> x(N, 0);  // 要素数Nのベクターx
  vector<int> y(N, 0);  // 要素数Nのベクターy
  double max_dist = 0;  // 答えは小数にもなる

  // 入力
  cin >> N;

  for (int i = 0; i < N; ++i) {
    cin >> x[i];
    cin >> y[i];
  }

  // 全探索　計算量N^2
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      // 距離の計算
      double calc = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
      // 最大値の更新
      if (max_dist < calc) {
        max_dist = calc;
      }
    }
  }
  // 出力
  cout << max_dist << endl;
}