https://www.luogu.com.cn/problem/UVA12762 题目给各位DaLao们翻译了:

题目描述:

设S是欧几里德平面上N个点的集合， 使得三个点是共线的， 且P是集合S中的N个点之一。 S的子集X生成一个P-huifx， 其中X至少包含3个点， 如果X的凸包在其边界上包含P。 计算生成P外壳的S子集的数量。

输入格式:

输入的第一行包含一个整数T(1<=T<=85) 测试用例的数量。 每个案例以（N=|S|3<=N<=1000）开始， 接下来的N行分别包含两个整数，X和Y， 测试案例contK的i-thf的模板(1<=i<=N,|X|,|Y|<=10000)。 我们点的指数P(1<=K<=N)。

输出格式:

对于每个测试用例，打印生成P-hull的S子集的数量。 输出计数mod 1000000009 （即，答案除以该数字的剩余部分）

注意:

欧几里德平面中集合Y的凸包是包含Y的最小凸集。 如果对象内的每一对点的连接线完全位于对象内部， 则对象是凸集。 凸面外壳可视为由围绕y轴上的点拉伸的橡皮筋形成的形状