#abc0164. [abc016_4]一刀両断
[abc016_4]一刀両断
问题文
高桥君通过训练学会了用空手刀劈断木板。给定表示空手刀轨迹的线段和木板形状的多边形,请计算木板被劈成几块。
输入
输入通过标准输入给出,具体格式如下:
:
- 第1行为以空格分隔的线段端点坐标 。
- 第2行为多边形的顶点数 。
- 接下来的N行为每个顶点的坐标 。
输入的线段和多边形满足以下条件:
- 多边形的顶点按逆时针顺序给出。
- 多边形的顶点与线段之间的距离大于等于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