题目描述

JYY有N个平面坐标系中的矩形。每一个矩形的底边都平行于X轴，侧边平行于Y轴。第i个矩形的左下角坐标为(Xi,Yi)，底边长为Ai，侧边长为Bi。现在JYY打算从这N个矩形中，随机选出两个不同的矩形，并计算它们的并的大小。JYY想知道，交的大小的期望是多少。换句话说即求在所有可能的选择中，两个矩形交的面积的平均大小是多大。

输入

输入一行包含一个正整数N。

接下来N行，每行4个整数，分别为Xi，Yi，Ai，Bi

2 < =  N < =  2*10^5, 0 < =  Xi, Yi, Ai, Bi < =  10^6。

输出

输出一行包含一个实数，表示矩形并的大小的期望。

样例输入

4

0 0 3 5

2 1 3 5

3 3 3 5

0 5 3 5

样例输出

1.833333333

---

题解

扫描线+二维树状数组区间修改区间查询

显然题目相当于：先给每个矩形内的权值+1，再查询每个矩形内的权值和即为任意选出两个矩形（可以相同，有顺序）的交面积的和，再减去每个矩形的面积（自己和自己）即得选出两个不同矩形的交面积之和。

那么我们把修改和询问差分成4个端点，就相当于统计每个询问拆出点的左下修改拆出点的贡献。使用扫描线维护。

注意到我们要做的是矩形加、矩形求和，可以使用  的方法，扫描线、一维树状数组方法类似。

最后除以 $n(n-1)$ 即可得到答案。

然而本题最恶心一点：本题爆long long！因此只能使用long double大法。由于最终答案只有 $10^{12}$ 级别，因此long double的精度是够的，不需要担心精度问题。

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

#include 
     
      #include 
      
       #include 
       
        #define N 200010using namespace std;typedef long double ld;int k;struct bit{	ld f[N << 2];	inline void add(int x , ld a)	{		int i;		for(i = x ; i <= k ; i += i & -i) f[i] += a;	}	inline ld ask(int x)	{		int i;		ld ans = 0;		for(i = x ; i ; i -= i & -i) ans += f[i];		return ans;	}}A , B , C , D;struct data{	ld x;	int y , z , val;	bool operator<(const data &a)const {return x < a.x;}}a[N << 1] , b[N << 1];ld v[N << 2];inline void modify(ld x , int y , int a){	A.add(y , a) , B.add(y , x * a) , C.add(y , v[y] * a) , D.add(y , x * v[y] * a);}inline ld query(ld x , int y){	return (x + 1) * (v[y] + 1) * A.ask(y) - (v[y] + 1) * B.ask(y) - (x + 1) * C.ask(y) + D.ask(y);}int main(){	int n , i , p = 1;	ld xi , yi , ai , bi , ans = 0 , sum;	scanf("%d" , &n) , sum = (ld)n * (n - 1);	for(i = 1 ; i <= n ; i ++ )	{		scanf("%Lf%Lf%Lf%Lf" , &xi , &yi , &ai , &bi) , ans -= ai * bi;		a[i].x = xi , a[i].y = yi , a[i].z = yi + bi , a[i].val = 1;		b[i].x = xi - 1 , b[i].y = yi - 1 , b[i].z = yi + bi - 1 , b[i].val = -1;		a[i + n].x = xi + ai , a[i + n].y = yi , a[i + n].z = yi + bi , a[i + n].val = -1;		b[i + n].x = xi + ai - 1 , b[i + n].y = yi - 1 , b[i + n].z = yi + bi - 1 , b[i + n].val = 1;		v[++k] = yi , v[++k] = yi + bi , v[++k] = yi - 1 , v[++k] = yi + bi - 1;	}	sort(v + 1 , v + k + 1) , k = unique(v + 1 , v + k + 1) - v;	for(i = 1 ; i <= 2 * n ; i ++ )	{		a[i].y = lower_bound(v + 1 , v + k + 1 , a[i].y) - v;		a[i].z = lower_bound(v + 1 , v + k + 1 , a[i].z) - v;		b[i].y = lower_bound(v + 1 , v + k + 1 , b[i].y) - v;		b[i].z = lower_bound(v + 1 , v + k + 1 , b[i].z) - v;	}	sort(a + 1 , a + 2 * n + 1) , sort(b + 1 , b + 2 * n + 1);	for(i = 1 ; i <= 2 * n ; i ++ )	{		while(p <= 2 * n && a[p].x <= b[i].x) modify(a[p].x , a[p].y , a[p].val) , modify(a[p].x , a[p].z , -a[p].val) , p ++ ;		ans += b[i].val * (query(b[i].x , b[i].z) - query(b[i].x , b[i].y));	}	printf("%.9Lf\n" , ans / sum);	return 0;}