BZOJ

分析

考虑对于每个矩形,求出其它矩形与它的交的面积之和。

我们把其它矩形都加上 $1$,然后统计该矩形内的和即可。

进一步可以得到这样一个做法:首先把所有矩形都加上 $1$,然后对于每个矩形统计它内部的和,减去它的面积即为所求。最后加起来除以 $n(n-1)$ 即为答案。

那么问题就在于怎么支持矩形加、矩形求和了。

有一个在线的做法是二维树状数组,但空间无法承受。因此可以考虑离线,用扫描线替代掉一维即可。

时间复杂度 $\mathcal{O}(n\log W)$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long double ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10,LIM=2000000+10;

int n,Q=0; ll ans=0;
struct opt { int op,x,l,r,w; } q[N<<2];
bool operator <(opt a,opt b) {
    if (a.x!=b.x) return a.x<b.x;
    else if (a.op!=b.op) return a.op<b.op;
    else return a.w<b.w;
}

struct Fenwick {
    ll c[LIM];
    inline void add(int x,ll w) { for (;x<LIM;x+=x&-x) c[x]+=w; }
    inline ll sum(int x) { ll s=0;
        for (;x;x-=x&-x) s+=c[x];
        return s;
    }
} A,B,C,D;
inline void modify(int x,int y,int w) {
    A.add(y,w),B.add(y,x*w),C.add(y,y*w),D.add(y,(ll)x*y*w);
}
inline ll query(int x,int y) {
    return A.sum(y)*(x+1)*(y+1)-B.sum(y)*(y+1)-C.sum(y)*(x+1)+D.sum(y);
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) {
        int x=read()+2,y=read()+2,a=read(),b=read();
        q[++Q]=(opt){1,x,y,y+b-1,1};
        q[++Q]=(opt){1,x+a,y,y+b-1,-1};
        q[++Q]=(opt){2,x-1,y,y+b-1,-1};
        q[++Q]=(opt){2,x+a-1,y,y+b-1,1};
        ans-=1ll*a*b;
    }
    sort(q+1,q+Q+1);
    for (re int i=1;i<Q;++i) {
        if (q[i].op==1)
            modify(q[i].x,q[i].l,q[i].w),modify(q[i].x,q[i].r+1,-q[i].w);
        else
            ans+=q[i].w*(query(q[i].x,q[i].r)-query(q[i].x,q[i].l-1));
    }
    printf("%.9Lf\n",ans/n/(n-1));
    return 0;
}
最后修改:2020 年 02 月 26 日 09 : 40 AM