[ARC004 A] 2点間距離の最大値

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

リーグ戦的な組み合わせでユークリッド距離を求める問題。

要点

• Nチームで1対1のリーグ戦を行うときの組み合わせの求め方
• ユークリッド距離の求め方

がわかればすぐ解ける。

あまりいけてない実装 (AC)

N = gets.to_i                                        # => 3
XY = N.times.collect { gets.split.collect(&:to_i) }  # => [[1, 1], [2, 4], [4, 3]]
s = []
N.times do |i|
  (i.next...N).each do |j|
    s << [XY[i], XY[j]]
  end
end
a = s.collect do |(x1, y1), (x2, y2)|
  Math.sqrt((x2 - x1)**2 + (y2 - y1)**2)             # => 3.1622776601683795, 3.605551275463989, 2.23606797749979
end
p a.max                                              # => 3.605551275463989

この実装では平方根を計算しすぎという点で TLE になってくれてもよかったが 100 ms 程度で通ってしまう。

リファクタリング後 (AC)

N = gets.to_i                                        # => 3
XY = N.times.collect { gets.split.collect(&:to_i) }  # => [[1, 1], [2, 4], [4, 3]]
max = XY.combination(2).collect { |(x1, y1), (x2, y2)|
  (x2 - x1)**2 + (y2 - y1)**2                        # => 10, 13, 5
}.max
p Math.sqrt(max)                                     # => 3.605551275463989

リーグ戦的な組み合わせには combination メソッドを使いたい。また平方根の呼び出しは最大面積を求めたあとで呼ぶと一回で済む。