洛谷P4460
n<20,试试状压
设 \(dp[i][j]\) 表示状态为i,最后一个点为j（当前在点j）。
枚举当前点为i，要转移的点为k
转移：$ dp[i|(1<<k-1)][k]+=dp[i][j] $
还需要判断一下三点连线在不在同一条直线上。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
int x=0,f=0;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f|=(ch=='-');
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f?-x:x;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+48);
}
const int Mod=1e8+7;
int n,m,dp[1<<20][20],ans;
int f[1<<20];
int map1[51][51];
int x[51],y[51];
bool ss(int a,int b,int c) {
return ((x[a]-x[b])*(y[b]-y[c])==(x[b]-x[c])*(y[a]-y[b]));
}
signed main(){
n=read();
for (int i=0;i<n;++i) {
x[i]=read(); y[i]=read();
}
for (int i=1;i<(1<<n);++i) {
f[i]=f[i>>1]+(i&1);
}
for (int i=0;i<n;++i) {
for (int j=0;j<n;++j) {
if (i==j) continue;
for (int k=0;k<n;++k) {
if (k==i||k==j) continue;
if ((((x[k]-x[i])*(x[k]-x[j])<0)||((y[k]-y[i])*(y[k]-y[j])<0))&&ss(i,k,j)) {
map1[i][j]|=(1<<k);
}
}
}
}
for (int i=0;i<n;++i) {
dp[1<<i][i]=1;
}
for (int i=1;i<(1<<n);++i) {
for (int j=0;j<n;++j) {
if(dp[i][j]&&((1<<j)&i)) {
if (f[i]>=4) ans=(ans+dp[i][j])%Mod;
for (int k=0;k<n;++k) {
if (!((1<<k)&i)&&(map1[j][k]&i)==map1[j][k]) {
dp[i|(1<<k)][k]=(dp[i|(1<<k)][k]+dp[i][j])%Mod;
}
}
}
}
}
cout<<ans;
return 0;
}