#2012. [USACO20FEB] Triangles S

[USACO20FEB] Triangles S

题目描述

Farmer John 想要给他的奶牛们建造一个三角形牧场。

有 NN(3≤N≤1053\leq N\leq 10^5)个栅栏柱子分别位于农场的二维平面上不同的点 (X1,Y1)…(XN,YN)(X_1,Y_1)\ldots (X_N,Y_N)。他可以选择其中三个点组成三角形牧场,只要三角形有一条边与 xx 轴平行或重合,且有另一条边与 yy 轴平行或重合。

FJ 可以组成的所有可能的牧场的面积之和等于多少?

输入格式

第一行包含 NN。

以下 NN 行每行包含两个整数 XiX_i 和 YiY_i,均在范围 −104…104−10^4\ldots 10^4 之内,描述一个栅栏柱子的位置。

输出格式

由于面积之和不一定为整数且可能非常大,输出面积之和的两倍模 109+710^9+7 的余数。

样例

4
0 0
0 1
1 0
1 2
3

题目来源:洛谷 P6149