SRM574 450

問題

正N角形の各頂点だけが配置されている。
ある頂点リストpoints(M個、N

考え方

bitDP。

蟻本の「3-4 動的計画法を極める！」と同じような感じで、dp[辿った頂点集合][今いる頂点]で2重ループで書ける。

今の辿った頂点集合stと今いる頂点vについて、まだたどっていない&交差する頂点wへ、配るdpをする。
交差する頂点は、今いる頂点から時計回り、反時計回りに一番近い辿っている頂点を探し、それが、vでないかどうかで判定できる。どちらかがvならば交差しない。
(vとwの間にたどった頂点があれば、そこからvとw以外の頂点への辺があるはずなので)