题意整理

• 有 (n) 个点（(n < 20)），给定坐标。
• 一个“画线方案”是连接若干点的折线路径，必须满足：
  1. 连接的点数至少为 4。
  2. 点不能重复使用。
  3. 两点之间的线段必须是直线（不能弯曲）。
  4. 如果从点 (A) 到点 (B) 的直线穿过另一个点 (C)（即 (C) 在线段 (AB) 上，且 (C \neq A,B)），则必须满足 (C) 已经在这条路径之前被访问过（即“使用过”），否则这个 (A \to B) 的移动是不允许的。
• 求所有满足条件的不同路径数量（不同顺序算不同方案），对 (100000007) 取模。

---

第一步：理解“跨点”规则

这是本题关键。
给定三个不同的点 (A,B,C)，如果 (C) 在线段 (AB) 上（按几何坐标，即 (C) 在 (A,B) 之间，共线且介于两点之间），那么要直接从 (A) 到 (B)，必须 (C) 已经被访问过。

例如九宫格里，从 1 直接到 3 必须经过 2，但若 2 未用过，则不允许；若 2 已经用过，则可以。

所以：在任意两点之间移动时，需要检查它们之间是否有“中间点”（在它们的线段上且不是端点），并且这个中间点是否已经访问过。

---

第二步：预计算中间点关系

令 (n \le 19)，我们可以预先计算：

对任意两点 (i,j)（不同），找出所有点 (k)（不是 (i,j)）使得 (k) 在线段 (ij) 上（几何上严格介于中间）。

判断三点共线且中间：
( \vec{ik} ) 与 ( \vec{ij} ) 同向且 (0 < \frac{|ik|}{|ij|} < 1)，用叉积判断共线，点积判断在中间。

为了方便，可以用整数运算（叉积=0且点积>0且点积<距离平方）。

---

设 (between[i][j]) 是一个位掩码（bitmask），表示从 (i) 到 (j) 的线段上严格在中间的点的集合（用二进制位表示点编号）。

如果 (between[i][j]) 不为空，则从 (i) 到 (j) 移动时，需要这些中间点全部已经在当前路径的访问集合中。

---

第三步：状态动态规划

我们要求的是不同的路径（序列），等价于求所有长度为 (L \ge 4) 的点序列（排列的子序列，但要求每个相邻跳转满足中间点条件）。

因为 (n) 只有 19，可以用状态压缩 DP。

定义： [ dp[mask][last] = \text{以 last 结尾，且访问点集为 mask 的路径数量} ] 其中 (mask) 是二进制掩码，表示已经访问的点集，(last) 是最后一个点的编号。

初始状态：(dp[1<<i][i] = 1)，表示从点 (i) 开始的路径。

---

转移： 从状态 ((mask, last))，尝试下一个点 (next)（不在 (mask) 中）。 检查从 (last) 到 (next) 是否允许：

• 找出 (between[last][next]) 的中间点掩码 (mid)。
• 要求 (mid \subseteq mask)（即所有中间点都已经访问过）。 若满足，则： [ dp[mask \mid (1<<next)][next] \ += dp[mask][last] ]

---

最终答案： [ ans = \sum_{mask: \text{popcount}(mask) \ge 4} \sum_{last} dp[mask][last] ]

---

第四步：复杂度

状态数：(2^n \times n)，这里 (n \le 19)，所以 (2^{19} \times 19 \approx 10^7)，可接受。

转移：每个状态尝试所有 (n) 个可能的下一步，每次检查中间点条件 (O(1))（因为已预计算位掩码）。

因此总复杂度 (O(2^n \times n^2)) 约 (5 \times 10^7)，在 2 秒内 C++ 可过。

---

第五步：实现细节

1. 预计算： 对每对 (i,j)，计算 (between[i][j])：

   • 叉积 ((P_k - P_i) \times (P_j - P_i) = 0) 且
   • 点积 ((P_k - P_i) \cdot (P_j - P_i) > 0) 且
   • 点积 ((P_k - P_i) \cdot (P_j - P_i) < |P_j - P_i|^2)。 则 (k) 在线段 (i,j) 中间。 用位掩码记录。

2. DP 循环：

   for mask = 1 to (1<<n)-1:
       for last = 0 to n-1:
           if not (mask>>last & 1) continue;
           for next = 0 to n-1:
               if (mask>>next & 1) continue;
               if (between[last][next] & ~mask) == 0:
                   dp[mask | (1<<next)][next] += dp[mask][last];
   

3. 统计答案： 枚举所有 (mask) 中 1 的个数 (\ge 4) 的状态，累加 (dp[mask][last])。

---

第六步：验证样例

样例 1：4 个点共线 (0,0),(1,1),(2,2),(3,3)。

两点之间有中间点时，必须中间点已访问。

• 1 到 3 中间有 2
• 1 到 4 中间有 2 和 3，所以必须 2 和 3 都访问过才能从 1 到 4。
• 等等。

计算符合题意的路径，结果应该是 8（给定）。

样例 2：4 个点 (0,0),(0,1),(0,2),(1,0)。 共线情况：前三个点纵坐标相同，1 到 3 中间有 2。 枚举会得到 18。

---

第七步：最终算法总结

1. 读入 (n) 个点坐标。
2. 对每对 ((i,j))，预计算 (between[i][j])（位掩码）。
3. 初始化 (dp[1<<i][i] = 1)。
4. 状压 DP 递推。
5. 统计长度 (\ge 4) 的路径总数。
6. 输出对 (100000007) 取模的结果。

---

最终公式/步骤：

设 (dp[S][u]) 表示已访问集合 (S)、最后访问点为 (u) 的路径数。
转移： [ dp[S \cup {v}][v] \ += dp[S][u], \quad \text{若 } between[u][v] \subseteq S ]

答案： [ \text{ans} = \sum_{|S| \ge 4} \sum_{u \in S} dp[S][u] ]

---

这样即可高效解决此题。