- 状态比较显然的状压 \(dp\) ,设 \(f[S][i]\) 表示连接 \(S\) 集合中的点,最后到的点是 \(i\) 的方案数.
- 转移时,枚举一个 \(j\notin S\) ,那么只要 \(i,j\) 连线没有跨过在 \(S\) 中的点,就可以转移, \(f[S|(1<<j)][j]+=f[S][i]\) .
- 可以 \(O(n^3)\) 预处理出每两个点连线跨过的点的集合.这样总时间复杂度为 \(O(2^n\cdot n^2)\) .
- 枚举集合时可以从小到大直接枚举,因为 \(S\) 只能转移到比它大的 \(S'\) ,所以从小到大本身就是一个合法的拓扑序.
#include<bits/stdc++.h>
inline int pos(int S,int i)
{
return (S>>i)&1;
}
using namespace std;
typedef long long ll;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
fh=-1,jp=getchar();
while (jp>='0'&&jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*fh;
}
const int P=1e8+7;
inline int add(ll a,int b)
{
return a+b>=P?a+b-P:a+b;
}
const int MAXN=20;
int n,x[MAXN],y[MAXN];
int Cross[MAXN][MAXN];
int f[(1<<MAXN)+10][MAXN+10];
int ans=0;
int count(int x)
{
int s=0;
while(x)
{
s+=(x&1);
x>>=1;
}
return s;
}
int main()
{
// freopen("data.in","r",stdin);
n=read();
for(int i=0; i<n; ++i)
x[i]=read(),y[i]=read();
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
if(i!=j)
for(int k=0; k<n; ++k)
{
if(i!=k && j!=k && x[i]<=x[k] && x[k]<=x[j] && y[i]<=y[k] && y[k]<=y[j] && (y[k]-y[i])*(x[k]-x[j])==(y[k]-y[j])*(x[k]-x[i]))
{
Cross[i][j]|=(1<<k);
Cross[j][i]|=(1<<k);
}
}
for(int i=0; i<n; ++i)
f[1<<i][i]=1;
int lim=(1<<n);
for(int S=1; S<lim; ++S)
for(int i=0; i<n; ++i)
if(pos(S,i) && f[S][i])
{
for(int j=0; j<n; ++j)
if(pos(S,j)==0 && ((S&Cross[i][j])==Cross[i][j]))
f[S|(1<<j)][j]=add(f[S|(1<<j)][j],f[S][i]);
}
for(int S=0; S<lim; ++S)
if(count(S)>=4)
{
for(int i=0; i<n; ++i)
ans=add(ans,f[S][i]);
}
cout<<ans<<endl;
return 0;
}