Triangles

题目描述

农夫 John 想为他的奶牛建造一个三角形的牧场。 农场的二维地图上有 $N$ 个栅栏柱（$3\le N\le 10^5$），位于互不相同的点 $(X_1, Y_1) \ldots (X_N, Y_N)$。他可以从中选择三个点作为三角形牧场的顶点，前提是该三角形的一条边平行于 $x$ 轴，另一条边平行于 $y$ 轴。 FJ 能构造出的所有可能牧场的面积之和是多少？

输入格式

第一行包含 $N$。 接下来 $N$ 行每行包含两个整数 $X_i$ 和 $Y_i$，都在范围 $-10^4 \ldots 10^4$（含端点）内，描述一个栅栏柱的位置。

输出格式

由于面积之和不一定是整数且可能非常大，请输出： 将面积之和乘以 2 后，再对 $10^9+7$ 取模所得的余数。

4
0 0
0 1
1 0
1 2

3

提示

SCORING: 测试点 2 满足 $N=200.$ 测试点 3-4 满足 $N\le 5000.$ 测试点 5-10 没有额外限制。

Fence posts $(0,0)$, $(1,0)$, and $(1,2)$ give a triangle of area $1$, while $(0,0)$, $(1,0)$, and $(0,1)$ give a triangle of area $0.5$. Thus, the answer is $2\cdot (1+0.5)=3.$ Problem credits: Travis Hance and Nick Wu

标签: USACO|2020|Silver

来源

USACO|2020|Silver