Rectangle-小米 Online Judge TCO 预选赛

矫情吗；* 2022-01-21 00:37 175阅读 0赞

## 题意：平面上有 n个点，每两个可以构成一个矩形。点 (x1,y1)，(x2,y2) 构成的矩形的左上角为(min(x1,x2),min(y1,y2))，右下角为 (max(x1,x2),max(y1,y2))。于是我们有了 n⋅(n−1) /2个矩阵，并把它们从 1 到n⋅(n−1) /2 依次标号。现在我们随机从这些矩阵中选出标号不同的两个，请问他们的面积交的期望是多少？答案对 1000000007 取模。 ##

## 分析：暴力枚举复杂度O（n^4），常数大，会超时，换个角度思考，考虑每个矩形的贡献。离散化+前缀和一下。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N=1005;
    const int mod=1000000007;
    int n,x[N],y[N],ox[N],oy[N],lx,ly,sum[N][N],ans;
    int S(int x1,int x2,int y1,int y2){
    	return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
    }
    int qp(int a,int b){
    	int res=1;
    	while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
    	return res;
    }
    int main(){
    	scanf("%d",&n);
    	for(int i=1;i<=n;++i){
            int xx,yy;
            scanf("%d%d",&xx,&yy);
    		x[i]=ox[i]=xx;
    		y[i]=oy[i]=yy;
    	}
    	///离散化
    	sort(ox+1,ox+n+1);
    	lx=unique(ox+1,ox+n+1)-ox-1;
    	sort(oy+1,oy+n+1);
    	ly=unique(oy+1,oy+n+1)-oy-1;
    	for(int i=1;i<=n;++i){
    		int xx=lower_bound(ox+1,ox+lx+1,x[i])-ox;
    		int yy=lower_bound(oy+1,oy+ly+1,y[i])-oy;
    		++sum[xx][yy];
    	}
    	///二维前缀和
    	for(int i=1;i<=lx;++i)
    		for(int j=1;j<=ly;++j)
    			sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        ///枚举每个矩形
    	for(int i=1;i<lx;++i)
    		for(int j=1;j<ly;++j){
                ///矩形面积
    			int area=1ll*(ox[i+1]-ox[i])*(oy[j+1]-oy[j])%mod;
    			///产生贡献的点对
    			int num=S(1,i,1,j)*S(i+1,lx,j+1,ly)+S(1,i,j+1,ly)*S(i+1,lx,1,j);
    			ans=(ans+1ll*area*num%mod*(num-1))%mod;
    		}
    	int t=n*(n-1)>>1;
    	ans=1ll*ans*qp(1ll*t*(t-1)%mod,mod-2)%mod;
    	printf("%d\n",ans);
    	return 0;
    }