题目按难度顺序排序。

C 合体

原题：P3147 [USACO16OPEN] 262144 P

\(O(n \times (V + \log n))\)

TODO:

\(O(n \log n)\)

TODO:

\(O(n)\)

TODO:

A 迷宫设计

注意到题目是特殊性质的最小生成树问题。直接 Kruskal 能获得没有什么分数的好成绩。

注意到，根据 Kruskal 算法的过程，每次选边必然是一排一起选。考虑优化这个过程。

把每一维度的边按照大小排序。不难发现这对答案没有影响。

类似归并的过程，每次选择两个维度中边权小的那一个选满。

时间复杂度 \(O(n \log n)\)。

D 三角形

令 \(under_{i,j}\) 为第 \(i\) 个点和第 \(j\) 个点连成的线段下方（不包括线段上的点）的个数。可以 \(O(n^3)\) 预处理。判断点在线段哪一侧可以使用叉乘。

不难发现，每个三角形内的点的个数为三个 \(under\) 加加减减，时间复杂度 \(O(1)\)。

总时间复杂度 \(O(n^3)\)。

细节一堆

B 体育场 IV

没有订正的欲望。