← 返回题目列表

AtCoder · relay2018_g

G. 公交车站和凸包

中文机器翻译题面 查看原题

配点 : 100 点

問題文

2 在维度平面上 有 N 巴士站。 第i 个公交车站的坐标是 (x_i, y_i) 。然而,x_i, y_i 均为整数。

潜伏,N 出 我想知道选择 3 或更多公交车站并计算所有选择方法的凸包面积(包含所有选定点的最小面积的凸多边形)的总和。 现在要求您代表 Snuke 查找该值。

然而,总面积 a/2 可以证明 a 总是一个整数,所以 请给出除以a 该值应乘以 10^9+7 后的余数。

制約

  • 3 ≤ N ≤ 2000
  • |x_i|, |y_i| ≤ 10000
  • (x_i, y_i) ≠ (x_j, y_j) (1 ≤ i < j ≤ N)
  • 给定的哪一点 3 点不在同一条直线上
  • 所有输入值均为整数 总面积的

入力

输入是按以下格式从标准输入给出的。

N
x_1 y_1
:
x_N y_N

出力

占总面积的 2 次 打印除以 10^9+7 后的余数。


入力例 1

4
0 0
1 0
-1 1
-1 -1

出力例 1

12
  • 1 第一点, 当选择第2 第一点, 当选择第3 点时,凸包的面积为 1/2 。
  • 1 第一点, 当选择第2 第一点, 当选择第4 点时,凸包的面积为 1/2 。
  • 1 第一点, 当选择第3 第一点, 当选择第4 点时,凸包的面积为 1 。
  • 2 第一点, 当选择第3 第一点, 当选择第4 点时,凸包的面积为 2 。
  • 1 第一点, 当选择第2 第一点, 当选择第3 第一点, 当选择第4 点时,凸包的面积为 2 。

因此,总面积为 1/2+1/2+1+2+2=6 。占总面积的 除以 2 次 打印除以 10^9+7 所得的余数 12 。


入力例 2

10
-3 1
2 3
-2 0
-3 2
-5 -5
1 -5
2 4
5 4
5 -3
-2 5

出力例 2

75282