点 \((x_1, y_1)\) と点 \((x_2, y_2)\) を結ぶ線分の距離は、以下の式で計算できます。

• \(\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\)

二重ループを用いて、線分の端点となる \(2\) 点を全探索します。 線分の距離を上の式を用いて計算し、距離が一番大きくなるものが答えです。

時間計算量は \(O(N^2)\) であり、十分高速です。

実装例 C++

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

double pow(double x) {
  return x * x;
}

double distance(double x1, double y1, double x2, double y2) {
  return sqrt(pow(x1 - x2) + pow(y1 - y2));
}

int main() {
  int n;
  cin >> n;
  vector<double> x(n), y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }

  double answer = 0.0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      double temp_distance = distance(x[i], y[i], x[j], y[j]);
      if (answer < temp_distance) {
        answer = temp_distance;
      }
    }
  }

  printf("%.5f\n", answer);
  return 0;
}