#P4357. Point

    ID: 2838 传统题 1000ms 512MiB 尝试: 16 已通过: 3 难度: 8 上传者: 标签>CF2500提高+/省选-补集计数自定义排序规则同向双指针复制数组处理环叉积点积乘法原理

Point

题目描述

给出平面上 nn 个点,保证没有两点重合或者三点共线。

现在另外给出两个点 P,QP,Q,请求出有多少个点集的凸包包含 P,QP,Q(在边界上也算做包含)。

为了简化,我们认为两个点的的凸包为两点之间的线段,此时只需要 P,QP,Q 均在线段上即可。

请将答案对 109+710^9+7 取模。

输入格式

第一行一个整数 nn,表示点的个数。

接下来 nn 行,每行两个整数 x,yx,y,描述一个点的坐标 (x,y)(x,y)。

接下来两行,每行两个整数,分别表示 PP 和 QQ 点的坐标。

输出格式

一行一个整数,表示答案。

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

提示

对于 100%100\% 的数据,1≤n≤3×1031\le n\le 3\times 10^3,∣x∣,∣y∣≤109|x|,|y|\le 10^9。

题目来源

没有写明来源。