RT。 用 $g_{i,j,s}$ 表示 $i$ 到 $j$ 连接是否经过集合 $s$ 里的一个点。

然后状压DP转移。

两个样例都只输出1。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e8+7;
const double eps=1e-5;
bool g[20][20][(1<<19)];
int n,res=0,f[(1<<19)][20],x[20],y[20];
inline int lowbit(int s){return s&(-s);}
inline bool check(int i,int j,int xx){
	int t=__lg(xx);t++;
    if((x[t] - x[i]) * (y[j] - y[i]) == (x[j] - x[i]) * (y[t] - y[i])  
       && min(x[i] , x[j])<=x[t] && x[t] <= max(x[i] , x[j])    
       && min(y[i] , y[j])<=y[t] && y[t] <= max(y[i] , y[j]))
        return false;
    return true;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)g[i][j][0]=1;
	for(int s=1;s<(1<<n);s++){
		for(int i=1;i<=n;i++){
			if(!(s&(1<<i-1))){
				for(int j=i+1;j<=n;j++)
					if(!(s&(1<<j-1)))
					    g[i][j][s]=(g[i][j][s-lowbit(s)]&&check(i,j,lowbit(s)));
			}
		}
	}
//	for(int s=1;s<(1<<n);s++){
//		for(int i=1;i<=n;i++){
//			if(!(s&(1<<i-1))){
//				for(int j=i+1;j<=n;j++)
//					if(!(s&(1<<j-1))){
//						cout<<i<<" "<<j<<" s:"<<s<<"\n";
//						for(int k=1;k<=n;k++)if(s&(1<<k-1))cout<<k<<" ";
//						cout<<"\n";
//						cout<<g[i][j][s]<<"\n";
//					}
//			}
//		}
//	}
	for(int i=1;i<=n;i++)f[(1<<i-1)][i]=1;
	for(int s=1;s<(1<<n);s++){
		for(int i=1;i<=n;i++){
			if((s&(1<<i-1))){
				for(int j=1;j<=n;j++)
				    if(!(s&(1<<j-1))){
				    	int ns=(s|(1<<j-1));
				    	if(g[i][j][((1<<n)-1)-s-(1<<j-1)])
						f[ns][j]+=f[s][i],f[ns][j]=(f[ns][j]%mod+mod)%mod;
				    }
			}
		}
	}	
	for(int s=0;s<(1<<n);s++){
		if(__builtin_popcount(s)<4)continue;
		for(int i=1;i<=n;i++)
			if(s&(1<<i-1))res+=f[s][i],res%=mod;
	}
	cout<<res<<"\n";
}