一队渔船从亚得里亚海的岛启航。每个渔船的位置在标准坐标系统中用一个点表示,而该岛用一个凸多边形表示。船通过无线电设备进行通信,而岛屿则代表无线电波的障碍。更确切地说,如果船A发送消息,当且仅当连接A和B的位置的线段不穿过该岛的内部(它允许有线段触摸岛屿的侧面和顶点),然后船B接收消息。
图1:在第一个示例测试中,船舶2,3,4和7将收到原始的无线求救电信号,而船舶6和8将收到中继消息。
当船A遇到麻烦时,它发送所谓求救信号求救。所有收到求救信号的船立即发送所谓的中继信息,重复船A需要帮助。如果船舶只接收到中继消息(而不是原来的求救消息),那么它什么也不发送。
给你N只船舶的位置(整数从1到n表示)和岛屿的位置。1号船发现自己有麻烦,发送求救信号。确定将接收原始求救信号或任何中继消息的船舶总数。
输入:
第一排整数n——船舶的数量
以下N行的第k行包含两个整数$X_k,Y_k$ ($−10^9≤X_k,Y_k≤10^9$)——第k个船的坐标。所有船舶都位于不同的坐标,而不是一个单一的船舶位于一侧或多边形内。
下面的行包含整数m ——描述该岛的凸多边形的顶点数。以下M行第k行一般包含两个整数xk,,yk, ——多边形的第k个顶点的坐标。多边形的顶点逆时针方向给出并形成一个凸多边形。没有两个相邻的边将是平行的。
输出:
将收到的消息之一的总船只数。
Scoring
| subtask | score | Limitations |
|---|---|---|
| 1 | 18 | $1≤n≤300,3\le m\le 300$ |
| 2 | 19 | $1≤n≤3000,3\le m\le 3000$ |
| 3 | 20 | $1≤n≤100000,3\le m\le 300$ |
| 4 | 43 | $1≤n≤1000000,3\le m\le 1000000$ |
样例:
input
99
6
8 5
10 8
8 8
-2 3
-1 5
9 1
0 1
-1 2
71
1
5 1
8 3
7 5
4 6
0 5
-1 3
output
6
input
4
-1 0
-3 -20
6 10
5 10
4
3 0
3 1
0 10
0 -10
output
2
