P5571 题解

· · 题解

注：本篇题解的做法是官方题解底下提到的开桶分段统计做法，复杂度较劣，要学习更加优秀的做法，请看官方题解。

题意：

求平面上 n 个点围成的 \binom{n}{3} 个三角形中面积第 k 小的三角形面积（三角形面积可以为 0）。
数据范围：n\le 800。

题解：

由于 n\le 800，而枚举 3 个不同的点又带着 \frac{1}{6} 的小常数。
所以是可以直接枚举所有三角形计算面积的。
计算面积可以直接使用叉积计算，不会的可以看这里。
现在的问题就是如何快速求出 k 大。

一个非常简单的想法就是将所有面积值存下来然后再 nth_element求。
但是注意到本题空间限制非常的紧，直接存肯定会爆，这种想法走不通。

另一种想法是开桶存三角形面积。
但是值域非常大，而且桶里的元素可能会非常多，照样行不通。
不过这种做法能非常容易拓展改进，比上一种做法灵活。
如果一个桶里装的不是面积恰好为一个值的三角形，而是面积大小在一段范围内的三角形，就可以开较少的桶，也就不会 MLE 了。
具体的，搞个阈值 B，第 i+1 个桶存面积大小为 \lbrack iB,(i+1)B) 的三角形个数。
这样通过一次枚举我们就能快速求出第 k 大的三角形面积范围。
再做一次然后把符合这段范围的三角形再加进另一个桶里进行计算就可以了。
显然第一次枚举确定出的范围的长度不会超过 B，所以第二个桶的大小只用开 B。

空间复杂度 O(\frac{w^2}{B}+B)。（其中 w 为值域）
时间复杂度 O(n^3)，可以通过。
我的代码里 B 取了 2^{20}，跑得比较快。

官方题解提到了将值域 w 开到 10^9 的设想试图卡掉这种做法。
但是其实是卡不掉的，就是把上面的两次枚举改成三次枚举而已，其他基本相似。

代码：

#include<bits/stdc++.h>
using namespace std;
const int Lim=1<<20;
typedef long long ll;
int t[1050000],n,k,x[888],y[888],K;
ll L,R;
inline ll Abs(ll x) {
    return x<0?-x:x;
}
int main() {
    cin>>n>>k;
    for(int i=1; i<=n; ++i)cin>>x[i]>>y[i];
    for(int i=1; i<=n; ++i)
        for(int j=i+1; j<=n; ++j) {
            ll c;
            for(int k=j+1; k<=n; ++k)
                c=Abs(1ll*(x[i]-x[j])*(y[i]-y[k])+1ll*(x[k]-x[i])*(y[i]-y[j])),t[c>>20]++;
        }
    for(int i=0,r=0; i<=1000000; ++i)
        if(r+t[i]>=k) {
            K=k-r,L=i*1ll<<20,R=(i+1)*1ll<<20;
            break;
        } else r+=t[i];
    memset(t,0,sizeof(t));
    for(int i=1; i<=n; ++i)
        for(int j=i+1; j<=n; ++j) {
            ll c;
            for(int k=j+1; k<=n; ++k) {
                c=Abs(1ll*(x[i]-x[j])*(y[i]-y[k])+1ll*(x[k]-x[i])*(y[i]-y[j]));
                if(c>=L&&c<R)t[c-L]++;
            }
        }
    for(int i=0,sm=0; i<Lim; ++i)
        if(sm+t[i]>=K)cout<<L+i<<'\n',exit(0);
        else sm+=t[i];
}

居然跑得比 O(n^2\log^2 n) 快很多？（逃

另外，感觉这个做法和基数排序的思想有一点像？