配点 : 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