PolygonTraversal

作者：欧阳思琦 钟知闲

关键词：状压dp 线段相交

题目简述

给你正$n$边形上的$n$个点，顺时针$1\sim n$编号，先给出一个不重复的点的序列$point$（下标从$0$开始），令$m = point.size()$，对于$i = 0\sim m - 2$，将$point[i]$与$point[i + 1]$之间连一条边。接下来要你将剩下的没有在$point$中的点加入进其中，并且每一个新加入的点与之前最后一个点连边，最后首尾再连一条边，但是加入的点的顺序有个要求，需要满足新加入的边与之前至少一条边相交（之前的边包括初始边以及在这之前加入的新边，相交在端点不算），计算满足条件的加入方案数。

$n\in[4,18],m\in[2,n - 1]$

算法

先考虑两个引理：

1. 在正$n$边形中，与线段$(a,b)$相交的线段必须满足两个点分别在$(a,b)$劈开来的两个半圈之内。
2. 在正$n$边形中，假设线段$(a,b)$要与之前的$point$中点连出的边相交，必定要满足$(a,b)$将$point$集合构成的多边形劈成了两半。

第一个引理很好证明，考虑第二个引理怎么证明。

假如$(a,b)$将$point$构成的多边形劈成了两半，也就是说两个半圈都有多边形的端点（这个是不包括$a,b$本身的），那么因为$point$中的点都是联通的，假如这两个半圈之间没有边相连，那么显然这个$point$是断开的，这是不合法的。

假如$(a,b)$与$point$之前连出的边相交，那么必定至少有一对点不在同一边，多边形也就被分成了两个部分。

考虑到$n\leq 18$，很容易想到压位用二进制来存储信息，设$f[i][j]$表示当前已经选了的点集为$i$，最后一个点是$j$的方案数，转移根据上面的引理，我们只需要枚举一个新点，判断新的这条线段两边是不是都有点集$i$中的点即可。

最后连回初始点的时候，只需要满足最后点和初始点不相邻即可保证线段相交。

状态$O(2^n n)$，转移$O(n)$，总时间复杂度就是$O(2^ n n^ 2)$，但是因为题目中的条件比较强，因此复杂度远远达不到上界，可以很轻松的跑出正解。同时，可以利用转移的点是环上一段连续区间，用前缀和优化状压DP，做到 $O(2^n n)$ 的复杂度。