2010-10-21 485.1 NHC SRM なんかテストランが間違ってたセット。 250 等差数列に対して、偶数を2で割り続けた結果の数列が与えられるので、元の数列を復元せよ、という問題。 先頭二つを全パターン試して、問題がないかチェックするだけ。 500 見てない。 1000 凸包が二つ与えられるので、外側の凸包の周囲の点を任意に選んだとき、自分から一番遠い凸包の点を結ぶ線分がもう一個の凸包と交差する確率を求めよ、という問題。 凸包の周囲の点から一番遠い点とは常に頂点になるので、各頂点に該当する範囲を求める。これは各線分の垂直二等分線を用いることで、判定できる。後はそれぞれの区間について、衝突するかどうかを判定する。もし両端が衝突する区間があればそれはすべて衝突する区間。(相手が凸包なので。)方端だけ衝突するなら、もう一方の端がどこかに編曲点として存在するので二分探索。そうでない場合は中間に衝突する区間があるかも知れないので適当に探してみる。