跪求大佬条一下，蒟蒻已经红温了

常规
1

1. 「CQOI2018」解锁屏幕

题目ID：20122必做题100分

最新提交：

Wrong Answer

5 分

历史最高：

Wrong Answer

5 分

时间限制: 1000ms

空间限制: 512000kB

题目描述

使用过 Android 手机的同学一定对手势解锁屏幕不陌生。 Android 的解锁屏幕由 3×33×3 个点组成，手指在屏幕上画一条线，将其中一些点连接起来，即可构成一个解锁图案。如下面三个例子所示：
image.png

题目描述

画线时还需要遵循一些规则：

  1. 连接的点数不能少于 44 个。也就是说只连接两个点或者三个点会提示错误。
  2. 两个点之间的联线不能弯曲。
  3. 每个点只能“使用”一次，不可重复。这里的“使用”是指手指划过一个点，该点变绿。
  4. 两个点之间的连线不能“跨过”另一个点，除非那个点之前已经被“使用”过。

对于最后一条规则，参见下图的解释。左边两幅图违反了该规则；而右边两幅图（分别为 2→4→1→3→62→4→1→3→6 和 6→5→4→1→9→26→5→4→1→9→2 ）则没有违反规则，因为在“跨过”点时，点已经被使用过了。
image.png
现在工程师希望改进解锁屏幕，增减点的数目，并移动点的位置，不再是一个九宫格形状，但保持上述画线规则不变。

请计算新的解锁屏幕上，一共有多少满足规则的画线方案。

输入格式

输入第一行为一个整数 nn ，表示点的数目。

接下来 nn 行，每行两个空格分开的整数 xixi​ 和 yiyi​ ，表示每个点的坐标。

输出格式

输出共一行，为题目所求方案数除以 108+7108+7 的余数。

样例

Input 1

4 0 0 1 1 2 2 3 3

Output 1

8

Input 2

4 0 0 0 1 0 2 1 0

Output 2

18

样例解释

样例解释 1

设 4 个点编号为 1 到 4 ，方案有 1→2→3→4→2→3→4 ， 2→1→3→4→1→3→4 ， 3→2→1→4→2→1→4 ， 2→3→1→4→3→1→4 以及它们的镜像。

数据范围

  • 对于 30%30% 的数据，1≤n≤10
  • 对于 100%100% 的数据，−1000≤xi,yi≤1000−1000≤xi​,yi​≤1000，1≤n<201≤n<20。各点坐标不相同。

WA5,样例不过

#include<bits/stdc++.h>
using namespace std;
#define x first;
#define y second;
const int mod=1e8+7;
int vec[25][25];
int n,dp[1<<20][25],li[1<<20];
pair<int,int> a[25];
void block1(){
  for(int i=0;i<(1<<n);i++){
    li[i]=li[i>>1]+(i&1);
  }
  int qx,qy,p1x,p1y,p2x,p2y;
  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(i==k||j==k)continue;
        qx=a[k].x;qy=a[k].y;
        p1x=a[i].x;p1y=a[i].y;
        p2x=a[j].x;p2x=a[j].y;
        bool f1=((p2x-p1x)*(qy-p1y)==(p2y-p1y)*(qx-p1x));
        bool f2=(min(p1x,p2x)<=qx)&&(max(p1x,p2x)>=qx);
        bool f3=(min(p1y,p2y)<=qy)&&(max(p1y,p2y)>=qy);
        if(f1+f2+f3==3)vec[i][j]|=(1<<k);
      }
    }
  }
  return;
}
int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i].x;cin>>a[i].y;
  }
  block1();
  for(int i=0;i<n;i++){
    dp[1<<i][i]=1;
  }
  int ans=0;
  for(int i=1;i<(1<<n);i++){
    for(int u=0;u<n;u++){
      if(dp[i][u]&&((1<<u)&i)){
        if(li[i]>=4)ans=(ans+dp[i][u])%mod;
        for(int k=0;k<n;k++){
          if(!((1<<k)&i)&&(vec[u][k]&i)==vec[u][k])dp[i|(1<<k)][k]=(dp[i|(1<<k)][k]+dp[i][u])%mod;
        }
      }
    }
  }
  cout<<ans;
  return 0;
}
2

已AC