Description
使用过Android手机的同学一定对手势解锁屏幕不陌生。Android的解锁屏幕由3x3个点组成，手指在屏幕上画一条
线将其中一些点连接起来，即可构成一个解锁图案。如下面三个例子所示：
画线时还需要遵循一些规则
1．连接的点数不能少于4个。也就是说只连接两个点或者三个点会提示错误。
2．两个点之间的连线不能弯曲。
3．每个点只能"使用"一次，不可重复。这里的"使用"是指手指划过一个点，该点变绿。
4．两个点之间的连线不能"跨过"另一个点，除非那个点之前已经被"使用"过了。
对于最后一条规则，参见下图的解释。左边两幅图违反了该规则：而右边两幅图(分别为2→4→1→3→6和→5→4→1→9→2)
则没有违反规则，因为在"跨过"点时，点已经被"使用"过了。
现在工程师希望改进解锁屏幕，增减点的数目，并移动点的位置，不再是一个九宫格形状，但保持上述画线的规则不变。
请计算新的解锁屏幕上，一共有多少满足规则的画线方案。
Input
输入文件第一行，为一个整数n，表示点的数目。
接下来n行，每行两个空格分开的整数xi和yi，表示每个点的坐标。
-1000≤xi,Yi≤l000，1≤n<20。各点坐标不相同
Output
输出文件共一行，为题目所求方案数除以100000007的余数。
Sample Input
4
0 0
1 1
2 2
3 3
0 0
1 1
2 2
3 3
Sample Output
8
解释：设4个点编号为1到4，方案有1→2→3→4，2→1→3→4，3→2→1→4，2→3→1→4，
及其镜像4→3→2→1,3→4→2→1,2→3→4→1,3→2→4→1.
解释：设4个点编号为1到4，方案有1→2→3→4，2→1→3→4，3→2→1→4，2→3→1→4，
及其镜像4→3→2→1,3→4→2→1,2→3→4→1,3→2→4→1.
Solution
一道挺简单的状压DP……
不知道CQ省选为什么会出状压板子题
先预处理出连接两点会经过哪些点
然后f[i][S]表示以i结尾，当前已经选中的点状态为S
从小到大枚举S进行转移
理论复杂度n^2*2^n，然而肯定跑不满就是了。
不知道CQ省选为什么会出状压板子题
先预处理出连接两点会经过哪些点
然后f[i][S]表示以i结尾，当前已经选中的点状态为S
从小到大枚举S进行转移
理论复杂度n^2*2^n，然而肯定跑不满就是了。
还有把1e-16写成-1e16这么丢人的事我才不会说╭(╯^╰)╮
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N (600000)
using namespace std;
int n,x[N],y[N],f[][N],line[][],ans,num[N]; double K(double x1,double y1,double x2,double y2)
{
if (x1==x2) return ;
if (y1==y2) return ;
return (y2-y1)/(x2-x1);
} int main()
{
scanf("%d",&n);
for (int i=; i<=n; ++i)
scanf("%d%d",&x[i],&y[i]); for (int i=; i<=n-; ++i)
for (int j=i+; j<=n; ++j)
{
line[i][j]=line[j][i]=(<<i-)|(<<j-);
for (int k=; k<=n; ++k)
{
if (abs(K(x[k],y[k],x[i],y[i])-K(x[j],y[j],x[i],y[i]))>1e-) continue;
if (!( x[k]>=min(x[i],x[j]) && x[k]<=max(x[i],x[j]) )) continue;
if (!( y[k]>=min(y[i],y[j]) && y[k]<=max(y[i],y[j]) )) continue;
line[i][j]|=(<<k-), line[j][i]=line[i][j];
}
} for (int i=; i<=n; ++i)
f[i][<<i-]=;
for (int i=; i<=(<<n)-; ++i)
for (int j=; j<=n; ++j)
if (i&(<<j-))
for (int k=; k<=n; ++k)
if (!(i&(<<k-)) && (((i|line[j][k])^(<<k-)))==i)
(f[k][i|(<<k-)]+=f[j][i])%=; for (int i=; i<=(<<n)-; ++i)
{
int x=i,cnt=;
for (int j=; j<=n; ++j){if (x&) cnt++; x>>=;}
if (cnt<) continue;
for (int j=; j<=n; ++j)
(ans+=f[j][i])%=;
}
printf("%d",ans);
}