Problem I

Problem I
1058: Chocolate
問題の概要
• 入力: 凸なN多角形 ( 3 < N <= 50 )
• 目的: 面積を半分にする線分のうち,
長さの最も短い, その長さ
方針
• 解析的に求める
– 一応本命のやり方？
– 三角形分割と, 三角形の等積変形
• マシンパワーでGo!
– 精度の問題があるが, 可能
– 全体を回転させ, それぞれを二分探索などする
• 重心を通ればよいわけではない (正三角形では？)
解析的に求める
• ある頂点に対し, 面積を半分に
するための反対側の点を探す
– ある頂点から見ていって, 半分を
超えるところを探す
– 三角形の中で, 比を使って反対
側の点を求める
• 等積変形を行う
– 直線の交点を求める
– 交点までの距離, 角度を求める
– これらを使って長さを計算できる
• 線分の長さの最小値を記憶
2
2
2
：
3
5
3
マシンパワーで
• X軸に平行な線分を使って図形を切る
yの最大
yの最小
• 後は, 全体を回転させてみればよい.
– 何やら, 0.1度くらいで十分らしいが…
松崎のプログラム
• 解析的に解くプログラム
• 170行くらい
– うち, ライブラリが40行くらい
• 時間にすると,
– 手を動かすのに, 30分くらい？
– コーディングには1時間はかかっていないはず

Download Report