P6149 [USACO20FEB] Triangles S - 洛谷 (luogu.com.cn)
题解：P6149 [USACO20FEB] Triangles S - 洛谷专栏 (luogu.com.cn)
对于一个点考虑它与它横坐标相等和纵坐标相等的点，假设有两个点与它横坐标相等，纵坐标小于它，另两个点与它纵坐标相等，横坐标小于它。假设与它横坐标相等的两个点离它的距离是 a,a+b，另外两个点离这个点的纵坐标的距离是 c,c+d，那么贡献就是 ac+a(c+d)+c(a+b)+(a+b)(c+d)=(2a+b)(2c+d))，一个另个相邻点的线段的贡献次数就是比他远的点的数量。
先按横坐标排序再按纵坐标排序，分别统计贡献，这里还要考虑不同的四个方向，对于横坐标排序预处理一个点往左右的贡献，纵坐标排序预处理一个点往上下的贡献，最后把贡献求和，就是把四个方向的答案相加。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,Mod=1e9+7;
int n,sum,ans,ly[N],ry[N],ux[N],dx[N];
struct node
{
int x,y,id;
}a[N];
bool cmp1(node x,node y)
{
if(x.x==y.x) return x.y<y.y;
return x.x<y.x;
}
bool cmp2(node x,node y)
{
if(x.y==y.y) return x.x<y.x;
return x.y<y.y;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i].x>>a[i].y,a[i].x+=1e4+5,a[i].y+=1e4+5,a[i].id=i;
sort(a+1,a+1+n,cmp1);
for(int i=1;i<=n;++i)
{
int m=i;
while(a[i].x==a[m+1].x) m++;
sum=0;
for(int j=i+1;j<=m;++j)
{
sum++;
ly[a[j].id]=ly[a[j-1].id]+sum*(a[j].y-a[j-1].y);
ly[a[j].id]%=Mod;
}
sum=0;
for(int j=m-1;j>=i;--j)
{
sum++;
ry[a[j].id]=ry[a[j+1].id]+sum*(a[j+1].y-a[j].y);
ry[a[j].id]%=Mod;
}
i=m;
}
sort(a+1,a+1+n,cmp2);
for(int i=1;i<=n;++i)
{
int m=i;
while(a[i].y==a[m+1].y) m++;
sum=0;
for(int j=i+1;j<=m;++j)
{
sum++;
ux[a[j].id]=ux[a[j-1].id]+sum*(a[j].x-a[j-1].x);
ux[a[j].id]%=Mod;
}
sum=0;
for(int j=m-1;j>=i;--j)
{
sum++;
dx[a[j].id]=dx[a[j+1].id]+sum*(a[j+1].x-a[j].x);
dx[a[j].id]%=Mod;
}
i=m;
}
for(int i=1;i<=n;++i) ans+=ly[i]*ux[i]+ly[i]*dx[i]+ry[i]*ux[i]+ry[i]*dx[i],ans%=Mod;
cout<<ans;
return 0;
}