← 返回题目列表

AtCoder · abc016_4

D. 一剑斩

中文机器翻译题面 查看原题

問題文

经过训练,高桥君现在能够用空手道砍木板了。给定代表空手道斩击轨迹的线段和代表棋盘形状的多边形,找出棋盘被切成多少块。


入力

输入是按以下格式从标准输入给出的。

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