比赛场次 464
比赛名称 USACO银组重赛hhh
比赛状态 已结束比赛成绩
开始时间 2020-03-02 18:00:00
结束时间 2020-03-02 22:00:00
开放分组 全部用户
注释介绍 前排%AK的dalao们
题目名称 Triangles(Silver)
输入输出 usaco_Feb_triangles.in/out
时间限制 2000 ms (2 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar梦那边的美好ET AAAAAAAAAA 0.234 s 19.00 MiB 100
Gravatar数声风笛ovo AAAAAAAAAA 0.629 s 16.41 MiB 100

Triangles(Silver)

★★   输入文件:usaco_Feb_triangles.in   输出文件:usaco_Feb_triangles.out   简单对比
时间限制:2 s   内存限制:256 MiB

【题目描述】

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 组