题目链接:https://code.mi.com/problem/list/view?id=151&cid=13
解题思路:
首先将x轴和y轴坐标离散化,然后就可以用二维前缀和求得每个格子被覆盖了几次,然后就可以求出每个格子的贡献,最后将总的贡献和乘以总的方案数的逆元即可。
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
const int mx = 1e3 + 10;
const int mod = 1000000007;
int n,x[mx],y[mx],f[mx][mx];
pa a[mx];
ll qpow(ll x,ll y){
ll ans = 1;
while(y){
if(y&1) ans = ans*x%mod;
x = x*x%mod;
y >>= 1;
}
return ans;
}
int main(){
scanf("%d",&n);
int r , c;
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
x[i] = a[i].x,y[i] = a[i].y;
}
sort(x+1,x+1+n);sort(y+1,y+1+n);
r = unique(x+1,x+1+n) - x;
c = unique(y+1,y+1+n) - y;
for(int i=1;i<=n;i++){
a[i].x = lower_bound(x+1,x+r,a[i].x) - x;
a[i].y = lower_bound(y+1,y+c,a[i].y) - y;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
int x1 = min(a[i].x,a[j].x);
int x2 = max(a[i].x,a[j].x);
int y1 = min(a[i].y,a[j].y);
int y2 = max(a[i].y,a[j].y);
f[x1][y1]++,f[x2][y2]++;
f[x1][y2]--,f[x2][y1]--;
}
}
ll ans = 0;
for(int i=1;i<r-1;i++){
for(int j=1;j<c-1;j++){
f[i][j] += f[i-1][j] + f[i][j-1] - f[i-1][j-1];
ll ret = 1ll*f[i][j]*(f[i][j]-1)/2%mod;
ans += ret*(x[i+1]-x[i])%mod*(y[j+1]-y[j])%mod;
ans %= mod;
}
}
ll ret = n*(n-1)/2;
printf("%lld\n",ans*qpow(ret*(ret-1)/2%mod,mod-2)%mod);
return 0;
}