全探索 atcoder

ARC004 A 2点間の最大距離

ARC004 A 2点間の最大距離
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/arc004/tasks/arc004_1

N個の点が与えられてそのうちの最大の2点間の距離を求める問題.

解説

Nが100と小さいので単純な2重ループで計算ステップ数は$10^4$なので余裕を持って間に合う.

計算量

$$O(N^2)$$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define MAX_N 101

Int N;
Vector2 points[MAX_N];

void input() {
  cin >> N;
  loop(n,0,N) cin >> points[n];
}

void solve() {
  double max_ = -1;
  loop(i,0,N-1) {
    loop(j,i+1,N) {
      max_ = fmax(max_, (points[i] - points[j]).length());
    }
  }
  cout << max_ << endl;
}

int main(void) {
  input();
  solve();
}