Hatena::ブログ(Diary)

cos65535の日記

2012-03-24

Hull Marathon (AOJ 2373)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2373

問題

解法

r_{n+1}=r_1とする。どの長さを使うかと、どの様に並べるかは全探索する。その二つが決まったら¥max_{¥theta}¥sum_{i=1}^n r_ir_{i+1}¥sin¥theta_iを制約条件¥sum_{i=1}^n ¥theta_i=2¥piの下で求め目れば良い。これはラグランジュの未定乗数法を使うと解くことが出来、結局¥cos ¥theta_i=¥frac{r_1r_2}{r_ir_{i+1}}¥cos¥theta_1,¥sum_{i=1}^n ¥theta_i=2¥piを満たすような¥thetaを二部探索で求めれば良いことになる。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/cos65535/20120324/1332600822
リンク元
Connection: close