#P3573. 「COCI 2021.12」Kućice

「COCI 2021.12」Kućice

题目描述

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

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

输入格式

第一行为一个整数 nn

接下来 nn 行,一行两个整数 xi,yix_i,y_i,表示有一个点是 (xi,yi)(x_i,y_i)

输出格式

输出每一个点集被凸包所包含的点数之和,对 109+710^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

数据范围与提示

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

Subtask 编号 分数 特殊限制
11 1010 所有点都在所有点的凸包边界上,n3n\ge 3
22 3030 除了第一个点,其他点都位于所有点的凸包边界上,n4n\ge 4x1=y1=0x_1=y_1=0
33 1010 n15n\le 15
44 3030 n100n\le 100
55 3030 无特殊限制