幾何コンに参加してました。
幾何苦手なんですが、３位でしたおどろき
A,Bはほとんど幾何の実装力要らなくて、Cは凸包が書ける程度の幾何力しか要らなかったし、ICPCを意識した幾何のコンテストというよりは幾何を題材にしたコンテストという感じだった。ただしDはICPCっぽい。
A
えっ
ソートするだけ・・・？
B
右側と左側に分けて重み付き二部マッチング
辺の重みは、対称形にする時と二つともY軸に持ってくる時のminを取る。
右側と左側の個数が釣り合わない場合は「Y軸に移動」みたいな頂点を作る。
最初、同じサイド同士の２つを対称に並べることに意味があると思い込んでいてかなり時間を取られた・・・両方Y軸に持ってくるよりも良くなると思いこんでた・・・
C
ちょっと考えると凸包を取ればいいと言うことが分かる。
x座標が区間に含まれる辺を見つけて来て、上下関係を調べたりする。
頂点の削除・二分探索が必要なのでデータ構造が要る。setでも間に合うのでsetがおすすめ。
あとは適当に頑張る。
D
ボス幾何問
満点はまず無理そう・・・
あとで部分点書いて復習しとかないとなー
