3355. [USACO20 Feb Silver]Triangles(Silver)

【题目描述】

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

有 $N$ $(3\le N\le 10^5)$ 个栅栏柱子分别位于农场的二维平面上不同的点 $(X_1, Y_1) \ldots (X_N, Y_N)$。他可以选择其中三个点组成三角形牧场，只要三角形有一条边与 $x$ 轴平行，且有另一条边与 $y$ 轴平行。

Farmer John 可以组成的所有可能的牧场的面积之和等于多少？

【输入格式】

第一行包含 $N$。 

以下 $N$ 行每行包含两个整数 $X_i$ 和 $Y_i$，均在 $[-10^4 , 10^4]$ 之内，描述一个栅栏柱子的位置。

【输出格式】

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

【样例输入】

4
0 0
0 1
1 0
1 2

【样例输出】

3

【样例解释】

栅栏木桩 $(0,0)$、$(1,0)$ 和 $(1,2)$ 组成了一个面积为 $1$ 的三角形，

$(0,0)$、$(1,0)$ 和 $(0,1)$ 组成了一个面积为 $0.5$ 的三角形。

所以答案为 $2\cdot (1+0.5)=3$。

【提示】

对于$ 10\% $的测试数据(测试点$ 2 $)，满足$ N = 200 $。 

对于$ 40\% $的测试数据(测试点$ 1\sim4 $)，满足$ N ≤ 5,000 $。 

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 二月公开赛 Silver 组