【模拟赛】立体几何（图论，三元环计数，四元环计数）_立体图论

题面

样例

1
4 6
1 2
1 3
1 4
2 3
2 4
3 4
1
2
3
4
5
6
7
8

69
1

样例图

题解

看到这个提示，我们应该大概能猜到用意了。

我们求的其实是最坏情况下的四点共面数，这个期望根本就™没用。

四点共面数好像挺复杂，我们分情况讨论吧：

• 我首先想到，如果两线段在三维空间中平行，那么四个端点一定共面。而中点恰好带来了平行的好条件：中位线。所以第一种情况：四元环的四条边中点——连成两个线段，分别与同一条对角线平行，所以两线段平行，四点共面；在样例中，可惜只有 3 种情况，目前离 69 还差得远。
• 然后我想到，如果存在三点共线，那么随便找一个第四点就能共面了，而三点共线只可能是一整条边。第二种情况：一条边中点&两端点 + 任意一点。这个情况就比较多了，我们只需要随便选 $m$ 条边之一，再从 $(n+m-3)$ 个点中选一个第四点，$m\cdot (n+m-3)$ 。样例中有 42 种情况。
• 上一条其实统计了所有“间”的情况（结点+中点+结点），通过有机化学的思路，我们其实早该想想“邻”的情况。这时，我们要保证不与“间”的情况重复，就只能是 “结点+结点+中点+中点” 。此时我们联想到 共用端点的两线段一定是共面的 ，于是，这种类别就对应了一个角。样例中每个点连了三条边，故总计 $4\cdot C_3^2=12$ 种。
• 四个中点，一个中点，两个中点的情况都讨论了，我们来讨论三个中点的情况。三中点+一结点，只能是在三角形内了。第四种情况：三元环三边中点+三结点之一。样例中共有 12 种。

四个结点是不可能的。

总计 69，和样例一致了，不管了