题解：P5571 [CmdOI2019] 高塔与晶石
Trafford1894
·
·
题解
关键词：叉积求三角形面积，优化空间
做这道题应当知道如何使用叉积求三角形面积。具体地，设 \vec{a}=(x_1,y_1),\vec{b}=(x_2,y_2), 有 \vec{a}\times \vec{b} = x_1\times y_2-x_2\times y_1。而根据叉积的几何意义有叉积是两个向量张成平面四边形的有向面积。求三角形面积时先除二再求绝对值即可。
注意到 \dbinom{n}{3} 约等于 8.5\times10^7，时限又有 2s，所以枚举三个点并不是瓶颈。但是 k 大值怎么求？如果把所有的面积全存下来再排序或者 nth_element，空间是 O(n^3) 的，会爆。
这时我们面对的问题和值域过大的桶排序类似，而后者可以用基数排序解决。考虑借鉴基数排序的思想，记 x_i\times y_i 的最大值为 w，本题中 w=10^{12}。设我们要将 w 划分为 p 进制，空间复杂度即是 O(p \log_p w) 的，时间复杂度是 O(n^3 \log_p w)。平衡一下取 p=\sqrt w=10^6 是两方面都可以接受的。
具体的实现过程就是先开一个 10^6 的桶，O(n^3) 枚举一遍，记计算出来的面积为 s，统计所有 \dfrac{s}{10^6} 的个数。由此，可以先确定 k 的一段范围，这个区间是小于 10^6 的；再枚举一遍，将在范围内的面积的出现次数用另一个桶统计出来，暴力计算即可。
记得开 long long！
AC 记录。