AtCoderのARC004のA問題をpythonで解きました。pythonの解答が見つからなかったので残しておきます。

環境

python3.4.3でときました

問題概要

問題文

平面上に N個の点があり、それぞれ 0から N−1までの番号が付けられており、それぞれの点について x座標と y座標が与えられています。その N点のうち 2点を選び結んで得られる線分のうち、最も長くなる線分の長さを求めてください。

2点間(x1,y1) (x2,y2)の線分の長さの公式は以下の通りです。

\sqrt{(x2 - x1)^2 + (y2 - y1)^2}

入力

N
x0 y0
x1 y1
・
・
・
xN−1 yN−1

制約

入力は N+1行ある。1行目には、点の個数を表す整数 N(2≦N≦100)が与えられる。2行目から N+1行までのi + 2(0≦i<N)行目には、i番の点の x座標を表す整数 xi(0≦xi≦100)と y座標を表す整数yi(0≦yi≦100)が空白を区切りとして与えられる。与えられる点のうち x座標と y座標がともに一致する点の組は存在しないが、2つの点を繋ぐ線分上に他の点が存在することはありうる。

入出力例

入力

出力

4.242641

ポイント

全探索で解く。for文を2回ネストさせる。
今回累乗をするときはpow()関数を使った。
またルートの計算にはmathライブラリのsqrt関数を使った。

コード例

import math
# nの値を取得
n = int(input())
# 座標はx座標はx、y座標はyと分けてリストに
x = list(range(n))
y = list(range(n))
for i in range(n):
  x[i],y[i] = map(int,input().split())
ans = 0
for j in range(n):
  for t in range(n):
    if math.sqrt(pow(x[t]-x[j],2) + pow(y[t] - y[j],2)) > ans:
       ans = math.sqrt(pow(x[t]-x[j],2) + pow(y[t] - y[j],2))
print(ans)

このコードだと座標上の同じ点どうしも計算してしまいますが同じ点は線分の長さ0になり結果には影響を与えません。

終わりに

もっと効率の良いコードがあるよという方(特に入力を受け付ける部分)はコメントで是非ご意見ください。