Luogu

LOJ

分析

状压 DP 。

设 $f[S][i]$ 表示已经使用了的点集为 $S$ ,现在在点 $i$ 的方案数。

转移直接枚举下一步往哪走即可。

注意到要走的时候路径上的点必须全部用过,那么可以预处理出 $i-j$ 跨过了哪些点。这个随便搞搞就行了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=20+10;
const int mod=1e8+7;

inline void add(int& x,int y) { x=(x+y)%mod; }

struct Point { int x,y; } p[N];
typedef Point Vector;
Vector operator -(Point a,Point b) { return (Vector){a.x-b.x,a.y-b.y}; }
inline int cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }

inline int check(int i,int j,int k) {
    if (p[i].x>p[j].x) swap(i,j);
    if (p[i].x==p[j].x) {
        if (p[k].x!=p[i].x) return 0;
        return p[k].y>=min(p[i].y,p[j].y)&&p[k].y<=max(p[i].y,p[j].y);
    } else {
        if (p[k].x<p[i].x||p[k].x>p[j].x) return 0;
        return cross(p[k]-p[i],p[j]-p[i])==0;
    }
}

int in[N][N],f[1<<20][N];

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) p[i].x=read(),p[i].y=read();
    for (re int i=1;i<=n;++i)
        for (re int j=i+1;j<=n;++j)
            for (re int k=1;k<=n;++k) {
                if (i==k||j==k) continue;
                if (check(i,j,k))
                    in[i][j]|=(1<<(k-1)),in[j][i]|=(1<<(k-1));
            }
    for (re int i=1;i<=n;++i) f[1<<(i-1)][i]=1;
    for (re int S=0;S<(1<<n);++S)
        for (re int i=1;i<=n;++i) {
            if (!f[S][i]) continue;
            for (re int j=1;j<=n;++j) {
                if (S&(1<<(j-1))) continue;
                if ((S&in[i][j])!=in[i][j]) continue;
                add(f[S|(1<<(j-1))][j],f[S][i]);
            }
        }
    int ans=0;
    for (re int S=0;S<(1<<n);++S) {
        if (__builtin_popcount(S)<4) continue;
        for (re int i=1;i<=n;++i) add(ans,f[S][i]);
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 14 PM