問題文
经过训练,高桥君现在能够用空手道砍木板了。给定代表空手道斩击轨迹的线段和代表棋盘形状的多边形,找出棋盘被切成多少块。
入力
输入是按以下格式从标准输入给出的。
A_x A_y B_x B_y N X_1 Y_1 X_2 Y_2 : X_N Y_N
- 1 线包含线段端点的坐标。 A_x,A_y,B_x,B_y 用空格分隔。 在
- 2 行显示多边形的顶点数。 给出了 N (3≦N≦100) 。
- 3 来自行 在 N 行中,每个顶点的坐标 X_i,Y_i 用空格分隔。 在
- 作为输入给出的坐标是 -1000 到 1000 之间的整数。
作为输入给出的线段和多边形满足以下属性。
- 多边形的顶点按逆时针顺序给出。
- 多边形的顶点与线段相距 0.1 或更多。
- 线段的端点距多边形 0.1 或更多。
- 线段的端点位于多边形外部。
- 多边形的三个连续顶点永远不会排成一条直线。
换句话说,不给出以下输入。
- A、B:多边形的顶点在线段上。
- C:线段的端点位于多边形的一边。
- D:多边形的边与线段重叠。
- E:线段的端点在多边形内部。
出力
输出板将被切割成多少块。在输出末尾添加换行符。
入力例1
-2 0 2 0 4 1 1 -1 1 -1 -1 1 -1
出力例1
2
入力例2
-3 1 3 1 8 2 2 1 2 1 0 -1 0 -1 2 -2 2 -2 -1 2 -1
出力例2
3