問題概要 凸多角形の辺上を速度xで、内部を速度yで動ける点が辺上の点から内部の点に移動する時間の最小値を求めよ。(頂点数) 解法 赤い辺が多角形の辺だとすると、真ん中の経路とるのであれば両端のどちらかの経路をとったほうがいいです(距離が適当な一次…

幾何ライブラリをちょっと整備したのでやってみた。解くたびにライブラリが増えるので生産性を感じる。それっぽい点を全部列挙して適当な線分がちゃんと多角形の中にあるかを判定する。O(2^n*n^4)で前処理がO(n^6)なのでTLEはやばそうだけどちゃんとbreakす…