読者です 読者をやめる 読者になる 読者になる

2008 Ruins

JOI

O(N^3)が想定だとずっと信じていたので必死に考える前に「幾何だ・・・」と思ってやめていましたが、どうやら他の人たちがみんなO(N^4)で解いていて時間的にもかなり余裕だという話を聞く前に、O(N^3)でときました。こっちは簡単。


解法としては、このコード(恥ずかしいので割愛)でやったのが

全点間の辺を双方向に、それぞれについてatan2したものでソート。ソートしたら
dp[i][j]:頂点iから始めて頂点jで終わる凸包(の一部)を作ったときの最大の可能な頂点数
でO(辺数×頂点数)のDPをしてやればなんとかなります。
180度のときがやっかいですが、dpをいつ更新したかも記録してれば何とかなります。