题目描述

译自 COCI 2021/2022 Contest #3 T5「Kućice」

给定平面上的 $n$ 个点，您需要求出每一个点集在凸包上或凸包内的点数之和，注意凸包有可能退化为一条线段，一个点，甚至空集，对 $10^9+7$ 取模的值。

输入格式

第一行为一个整数 $n$。

接下来 $n$ 行，一行两个整数 $x_i,y_i$，表示有一个点是 $(x_i,y_i)$。

输出格式

输出每一个点集被凸包所包含的点数之和，对 $10^9+7$ 取模。

1
5 5

1

3
-1 -1
1 -1
0 1

12

5
0 0
-1 0
2 -1
3 2
0 3

83

数据范围与提示

对于全部数据，$1\le n\le 1000$，$|x_i|,|y_i|\le 10^6$，不存在三点共线，不存在重点。