问题 D: Triangles

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:49 通过:13

题目描述

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

有 N 个栅栏柱子分别位于农场的二维平面上不同的点 (X1,Y1)…(XN,YN)。

他可以选择其中三个点组成三角形牧场,只要三角形有一条边与 x 轴平行,且有另一条边与 y轴平行。

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

输入格式

第一行包含 N。

以下 N 行每行包含两个整数 Xi 和 Yi,均在范围 −104…104之内,描述一个栅栏柱子的位置。

输出格式

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



数据范围

3≤N≤105



输入样例:

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⋅(1+0.5)=3


输入样例 复制

4
0 0
0 1
1 0
1 2

输出样例 复制

3