题解

什么破题，看一眼就能想出来\(n^2 2^n\)看了一眼数据范围有点虚，结果跑得飞快= =

处理出\(a[i][j]\)表示从\(i\)到\(j\)经过的点的点集

然后\(f[i][S]\)表示最后一个点在\(i\)处，经过的点集为\(S\)，方案数是多少

然后枚举一个不在\(S\)中的点\(j\)看看\(a[i][j]\)是否全部被\(S\)包含即可

代码

#include 
    
     #define fi first#define se second#define pii pair
     
      #define pdi pair
      
       #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')#define eps 1e-8#define mo 974711#define MAXN 1000005//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template 
       
        void read(T &res) {    res = 0;    char c = getchar();    T f = 1;    while (c < '0' || c > '9') {        if (c == '-') f = -1;        c = getchar();    }    while (c >= '0' && c <= '9') {        res = res * 10 + c - '0';        c = getchar();    }    res *= f;}template 
        
         void out(T x) {    if (x < 0) {        x = -x;        putchar('-');    }    if (x >= 10) {        out(x / 10);    }    putchar('0' + x % 10);}const int MOD = 100000007;int N, pos[(1 << 20) + 5];int a[25][25];int f[21][(1 << 20) + 5], cnt[(1 << 20) + 5];struct Point {    int x, y;    Point(int _x = 0, int _y = 0) {        x = _x;        y = _y;    }    friend Point operator+(const Point &a, const Point &b) { return Point(a.x + b.x, a.y + b.y); }    friend Point operator-(const Point &a, const Point &b) { return Point(a.x - b.x, a.y - b.y); }    friend int operator*(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; }    friend int dot(const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; }    int norm() { return x * x + y * y; }} P[25];int inc(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }int mul(int a, int b) { return 1LL * a * b % MOD; }int lowbit(int x) { return x & (-x); }void update(int &x, int y) { x = inc(x, y); }void Solve() {    read(N);    for (int i = 1; i <= N; ++i) {        read(P[i].x);        read(P[i].y);    }    for (int i = 1; i <= N; ++i) {        for (int j = i + 1; j <= N; ++j) {            a[i][j] |= (1 << i - 1) | (1 << j - 1);            for (int k = 1; k <= N; ++k) {                if (k == i || k == j) continue;                if ((P[k] - P[i]) * (P[j] - P[i]) == 0 && dot(P[k] - P[i], P[j] - P[i]) >= 0 &&                    (P[k] - P[i]).norm() < (P[j] - P[i]).norm()) {                    a[i][j] |= (1 << k - 1);                }            }            a[j][i] = a[i][j];        }    }    for (int i = 0; i < N; ++i) pos[1 << i] = i + 1;    for (int i = 1; i <= N; ++i) {        f[i][1 << i - 1] = 1;    }    for (int S = 1; S < (1 << N); ++S) {        for (int T = S; T; T -= lowbit(T)) {            int h = pos[lowbit(T)];            if (!f[h][S]) continue;            for (int j = 1; j <= N; ++j) {                if ((S & (1 << j - 1)) == 0) {                    if ((a[h][j] & (S | (1 << j - 1))) == a[h][j]) update(f[j][S ^ (1 << j - 1)], f[h][S]);                }            }        }    }    int ans = 0;    for (int S = 1; S < (1 << N); ++S) {        cnt[S] = cnt[S - lowbit(S)] + 1;        if (cnt[S] >= 4) {            for (int i = 1; i <= N; ++i) update(ans, f[i][S]);        }    }    out(ans);    enter;}int main() {#ifdef ivorysi    freopen("f1.in", "r", stdin);#endif    Solve();    return 0;}