ページ

2012/06/16

[競技プログラミング][PHP][AtCoder]2点間距離の最大値

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

時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB

問題文

平面上に N 個の点があり、それぞれ 0 から N−1 までの番号が付けられており、
それぞれの点について x 座標と y 座標が与えられています。
その N 点のうち 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 つの点を繋ぐ線分上に他の点が存在することはありうる。

出力

N 点のうち 2 点を選び結んで得られる線分のうち、最も長い線分の長さを標準出力に 1 行で出力せよ。
誤差は絶対誤差あるいは相対誤差の少なくとも片方が 10^−3 以下であれば許容する。
なお、最後には改行を出力せよ。

出典

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

回答

AtCoder/arc004_1.php at master · wada811/AtCoder · GitHub
問題ページに式まで書いてあるのでpow関数とsqrt関数でそのとおりに計算するだけ。

A問題は簡単だったけどB問題で最小を求めるロジックが思い浮かばなかった。
そのうち他の人のコードを見てロジックを確認したい。悔しい。