题目链接
题解
很水的装压dp，相信没人需要看题解....
dp[i][j]表示状态为i最后一个到的点为j,然后转移就很好写了
不过 我读入优化没读负数 ,为什么mod1e8 +7，我 mod 1e9 + 7 啊，WA了两发
#include<cstdio>
#include<vector>
#include<algorithm>
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-')f = -1; c = getchar();}
while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar();
return x * f;
}
#define mod 100000007
int n;
const int maxn = 21;
struct node {
int x,y;
bool operator < (const node &a)const {
if(x == a.x) return y < a.y;
return x < a.x;
}
} loc[maxn];
int dp[(1 << maxn) + 7][maxn];
int po[maxn][maxn];
void get(node x,node y,int X,int Y) {
int a = y.y - x.y , b = x.x - y.x , c = y.x * x.y - x.x * y.y;
int tmp = 0;
for(int i = X + 1;i < Y;++ i) {
if(loc[i].x * a + loc[i].y * b + c == 0)
tmp |= (1 << i);
//if(i != Y)vec[X].push_back(i); if(i != X)vec[Y].pish_back(i);
}
po[X][Y] = tmp | (1 << X); // ^ (1 << Y);
po[Y][X] = tmp | (1 << Y); // ^ (1 << X);
//printf("%d
",tmp);
}
int main() {
n = read();
for(int i = 0;i < n;++ i)
loc[i].x = read(),loc[i].y = read();
std::sort(loc,loc + n);
for(int i = 0;i < n;++ i)
for(int j = i + 1;j < n;++ j)
get(loc[i],loc[j],i,j);
int ans = 0;
for(int i = 0;i < n;++ i) dp[1 << i][i] = 1;
for(int i = 0;i < (1 << n);++ i) {
//ans = 0;
for(int j = 0;j < n;++ j) {
if(((1 << j) & i)) continue;
for(int k = 0;k < n;++ k) {
if(!((1 << k) & i)) continue;
if((po[k][j] & i) == po[k][j]){dp[i | (1 << j)][j] = (dp[i | (1 << j)][j] + dp[i][k]) % mod;}
}
}
}
for(int K,i = 0;i < (1 << n);++ i) {
K = 0;
for(int t = i;t;t >>= 1) if(t & 1)K ++;
if(K >= 4) {
for(int k = 0;k < n;++ k)
ans = (ans + dp[i][k]) % mod;
}
}
printf("%d
",ans);
return 0;
}