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を二部探索で求めれば良いことになる。