【AtCoder版！蟻本】ARC004 A - 2点間距離の最大値【準備編】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210317161018p:plain
AtCoder版！蟻本の準備編で類題としてあげられているARC004 AをPythonで解いていきます。

リンク

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

問題文

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

入力

・入力は N+1 行ある。
・1 行目には、点の個数を表す整数 N(2≦N≦100)が与えられる。
・2 行目から N+1 行目までの i+2(0≦i

解答例

n = int(input())

X = []
Y = []
for i in range(n):
    x, y = map(int,input().split())
    X.append(x)
    Y.append(y)

# 最長の線分
ans = 0

# 全探索
for i in range(n-1):
    for j in range(i,n):
        tmp = (X[i] - X[j])**2 + (Y[i] - Y[j])**2
        ans = max(ans,tmp**0.5)

print(ans)

解説

x,y座標の組がn点与えられ、その2点をつなぐ線分のうち最も長い線分の長さを答える問題です。

nが100以下と数が少ないので全探索すれば答えが求まります。

2重ループで異なる2点のすべての組み合わせを試します。
2点間の距離は(xi - xj)^2 + ( yi - yj)^2の平方根になりますので、tmpに(xi - xj)^2 + ( yi - yj)を代入します。
その後、ansとtmp^0.5を比較して大きいほうをansとします。

すべての点の組み合わせを探索し終えると求める解答となります。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク