题意
FJ 有 $n$ 个木桩，在这 $n$ 个木桩中任意选出三个，如果这三个组成的三角形是直角三角形且两个直角边分别平行 $x$，$y$ 轴的话就将答案加上这个三角形的面积的两倍。
思路
1.遇事不决先暴力(得分:30pts)
$O(n^3)$ 的暴力很好写，只需要枚举这三个木桩，在判断组成的三角形是否符合要求，统计答案即可。
2.一个看似没用的优化(得分：还是30pts)
我们可以将所有的坐标都加一个 10001 使其全部变为正数，我们在设两个vector 数组 $hx_{maxx}$ 和 $hy_{maxx}$，$hx_{X,j}$ 表示第 $j$ 个 x 坐标为X的木桩的编号。记录了这个数组后，我们就可以不用遍历那些不符合条件的木桩编号了。我们先枚举 x 坐标，然后再从所有x坐标为我们枚举到的值的木桩中找出任意两个，再枚举所有 y 坐标等于找到的第二个木桩的 y 坐标的木桩，最后统计答案即可。
3.非常重要的一步(得分：50pts)
我们发现上面的算法中，相当于枚举了 x 坐标相同的每个点。我们假设所有的x坐标相同的任意两个点组成的边的长度分别为:
$lenx_1,lenx_2,lenx_3 ...$，
这两个x坐标相同的点中的第二个的y坐标与所有相同y坐标的点组成的边的长度分别为:
$leny_1,leny_2,leny_3 ...$
很明显，
$ans=$
$ lenx_1 \times leny_1 + lenx_1 \times leny_2 + lenx_1 \times leny_3 + ... $
$+ lenx_2 \times leny_1 + lenx_2 \times leny_2 + lenx_2 \times leny_3 + ...$
$... $
根据乘法分配律，上面的式子显然等于：
$(lenx_1+lenx_2+lenx_3+ ... ) \times leny_1$
$+(lenx_1+lenx_2+lenx_3+ ... ) \times leny_2$
$+(lenx_1+lenx_2+lenx_3+ ... ) \times leny_2$
$... $
举个例子
假设我们有这样的情况：
答案显然是1号点到2号、3号点的距离和乘以1号到4号的距离加上1号点到2号、3号点的距离和乘以1号到5号的距离。只要我们预处理出点1、2、3号点到其他 y 坐标与其相等的点的距离和，就可以去掉一个循环。
如何预处理呢？
我们可以暴力求出1号点到其他y坐标与其相同的点的距离和——很显然是6。然后我们可以递推地求出2、3号点的距离和。
为了方便，我们将视野只放在 y 坐标为3的这一行，我们设 $left_i$ 为第i个点的左边的点的个数（包含第 $i$ 个点），$right_i$ 为第 $i$ 个点右边的点的个数(不包括第 $i$ 个点)，$sum_i$ 表示第 $i$ 个点到其他的点的距离和。
那么我们可以得到递推式：
$sum_i=sum_{i-1}+left_{i-1} \times dis(i,i-1+right_{i-1} \times dis(i,i-1))$
$dis(i,i-1)$ 表示第 $i$ 个点到第 $i-1$ 个点的距离。
4.终于迎来了正解
我们发现刚才的第2部分的式子还可以整理为
$(lenx_1+lenx_2+lenx_3 + ... ) \times (leny_1+leny_2+leny_3 + ... )$
在代码中就是我们已经预处理了x坐标，还可以预处理y坐标一次。
AC代码
#include<bits/stdc++.h>
#pragma G++ optimize(3)
using namespace std;
#define Mod 1000000007
const int maxn=100010,maxx=20010;
struct E{
int x,y;
}a[maxn],b[maxn];
struct KKK{
int l,r;
long long sum;
};
vector<KKK>bx[maxx],by[maxx];
int n,sum;
long long ans;
vector<int>hx[maxx],hy[maxx];
map<pair<int,int>,int>mp;
bool cmpx(E x,E y){
return x.x<y.x;
}
bool cmpy(E x,E y){
return x.y<y.y;
}
void init(){
sort(a+1,a+n+1,cmpx);
sort(b+1,b+n+1,cmpy);
for(int i=1;i<=n;i++){
int x=a[i].x,y=a[i].y;
int X=b[i].x,Y=b[i].y;
hy[y].push_back(i);
hx[X].push_back(i);
bx[y].push_back(KKK{0,0,0});
by[X].push_back(KKK{0,0,0});
mp[{X,Y}]=by[X].size()-1;
}
for(int i=1;i<=20001;i++){
if(!bx[i].size()||bx[i].size()==1)continue;
long long tmp=0;
for(int j=1;j<hy[i].size();j++){
tmp+=abs(a[hy[i][j]].x-a[hy[i][0]].x)%Mod;
tmp%=Mod;
bx[i][j].l=j;bx[i][j].r=bx[i].size()-j-1;
}
bx[i][0].sum=tmp;
bx[i][0].l=0;bx[i][0].r=bx[i].size()-1;
for(int j=1;j<bx[i].size();j++){
long long kkk=abs(a[hy[i][j]].x-a[hy[i][j-1]].x);
bx[i][j].sum=bx[i][j-1].sum;
bx[i][j].sum+=(bx[i][j-1].l+1)*kkk;
bx[i][j].sum-=(bx[i][j-1].r)*kkk;
bx[i][j].sum%=Mod;
}
}//_________________________________________________________
for(int i=1;i<=20001;i++){
if(!by[i].size()||by[i].size()==1)continue;
long long tmp=0;
for(int j=1;j<hx[i].size();j++){
tmp+=abs(b[hx[i][j]].y-b[hx[i][0]].y)%Mod;
tmp%=Mod;
by[i][j].l=j;by[i][j].r=by[i].size()-j-1;
}
by[i][0].sum=tmp;
by[i][0].l=0;by[i][0].r=by[i].size()-1;
for(int j=1;j<by[i].size();j++){
long long kkk=abs(b[hx[i][j]].y-b[hx[i][j-1]].y);
by[i][j].sum=by[i][j-1].sum;
by[i][j].sum+=(by[i][j-1].l+1)*kkk;
by[i][j].sum-=(by[i][j-1].r)*kkk;
by[i][j].sum%=Mod;
//if(by[i][j].sum<0)cout<<"kkkasdf"<<endl;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y;scanf("%d%d",&x,&y);
x+=10001;y+=10001;
a[i].x=x;a[i].y=y;
b[i].x=x;b[i].y=y;
}
init();
for(int i=1;i<=20001;i++){
if(!bx[i].size())continue;
for(int j=0;j<bx[i].size();j++){
long long tmp=bx[i][j].sum%Mod;
int X=a[hy[i][j]].x;
ans+=(tmp*by[X][mp[{X,i}]].sum)%Mod;
ans%=Mod;
}
}
cout<<ans%Mod;
return 0;
}