AOJ 2443 : ConvexCut
問題↓
最遅コードを叩きだしたので上げます。
間違いなく想定解法ではありません。
問題概要
- 凸多角形が与えられれます。
- 凸多角形の内部にある点のうち
そこから伸びる直線で多角形をカットした際に出来る2つの多角形の面積が等しいような点の座標を出力して下さい。 - ない場合は"NA"
- 頂点数 N = 50
解法
- まず、全ての頂点に対してそこから直線を伸ばして多角形を真っ二つにできるような直線を二分探索で求める。
- 直線を2つ選んで交点を出したいが、この時
一番誤差の少なそうな直線を選択する。
（具体的に言うと、最も線分の情報となる2点の距離が長いものを2つ選ぶ
その2つが同一直線でないものとなるようにしっかり処理する） - 選んだ2つの直線から出た交点から、
各辺を SPLIT 等分した全ての点に対し直線を作り、
それで実際にconvex_cutした結果真っ二つになっているかを調べる。 - 全てのconvex_cutの結果が 真っ二つになっていればその交点を出力する。
- 誤差をとにかく減らすため eq とかいろいろ小手先の努力をする。
ソースコード
感想
様による解法によると
点Pを通る任意の直線で凸多角形を切って面積が半分になるのは頂点数が偶数 かつ 平行で長さの等しい辺だけで構成されているとき.
らしいです。
ふぁああああ
