#P4441. [Swerc2015]Saint John Festival

    ID: 3646 传统题 1000ms 512MiB 尝试: 44 已通过: 20 难度: 6 上传者: 标签>难度分类普及+/提高-计算几何凸包Andrew 算法凸多边形二分查询叉积CF1900

[Swerc2015]Saint John Festival

[SWERC 2015] Saint John Festival

题目描述

圣约翰节放飞了许多天灯。给出一些大天灯和小天灯在平面上的位置,高度忽略不计。

如果某盏小天灯位于至少一个由三盏大天灯构成的三角形内部或边界上,就把它计入答案。一盏小天灯即使落在多个这样的三角形内,也只计一次。求计入的小天灯数。

输入格式

第一行一个整数 LL(3≤L≤10 0003\le L\le10\,000)。随后 LL 行,每行两个整数 x,yx,y,表示一盏大天灯的位置。

接下来一行一个整数 SS(1≤S≤50 0001\le S\le50\,000)。随后 SS 行,每行两个整数 x,yx,y,表示一盏小天灯的位置。

所有输入坐标均满足 0≤x,y≤2300\le x,y\le2^{30}。全部点互不相同,并且至少存在三个不共线的大天灯。

输出格式

一行一个整数,表示符合要求的小天灯数。

样例 #1

样例输入 #1

8
3 4
2 8
5 4
1 8
4 7
3 10
11 2
7 3
6
5 12
3 7
3 3
4 5
0 4
2 6

样例输出 #1

3

样例中的大小天灯与部分三角形;黑色方块是小天灯,红色圆点是大天灯