はてなブックマーク

猫の出没する範囲を調べました。猫が出没する場所を最小の面積で囲む境界を考え、その面積を求めてください。 入力として、最初に頂点の数が与えられます。頂点の数は1から100までです。次に、頂点の座標が与えられます。頂点の座標は空白と改行で区切られます。 出力として、猫の行動範囲の面積を小数点以下2桁までの精度で示してください。 サンプル入力 14 0 0 3 0 4 0 5 1 4 2 5 3 6 6 4 4 0 4 0 6 6 0 2 2 0 7 1 6 サンプル出力 39.00 まず、猫が出没する場所を最小の面積で囲む境界を求めなくてはなりません。このような境界のことを凸包(convex hull)といいます。 なお、凸包は面積が最小であるだけでなく、面積を囲うための最小の長さの線分となります。凸包は、すべての点を囲む最小の凸多角形です。 凸包を求める包装アルゴリズム(package wr