观察：答案的上界是每一维的前 $\frac{n}{3}$ 大之和减去前 $\frac{n}{3}$ 小之和的两倍。

我们可以直接把所有坐标排序后三等分，变为 $0,1,2$，则要达到上界，每个三角形都必须包含横坐标为 $0,2$ 的点和纵坐标为 $0,2$ 的点。事实上我们可以做到每个三角形中横纵坐标的集合分别是 $\{0,1,2\}$ 的排列。我们只需要证明在每个横坐标的纵坐标的出现次数都是 $\frac{n}{3}$ 的前提下，能够选出这样的三个点，则递归构造即可。实际上这就是正则二分图完美匹配这个经典问题，结论是完美匹配一定存在。因此这个题目可以从三个点推广到任意 $k$ 个点。

实现时可以直接暴力枚举 $3!$ 种排列。时间复杂度 $O(n)$。