第 016 场 AtCoder Beginner Contest
D
一刀両断
AtCoder
⌀ 1305
原题
← C→
翻译中…

Problem Statement

翻译中…

高橋くんは鍛錬の結果、空手チョップで木の板を切断できるようになりました。空手チョップの軌道を表す線分と板の形を表す多角形が与えられるので、板がいくつに切断されたか求めてください。

翻译中…

Input

翻译中…

入力は以下の形式で標準入力から与えられる。

翻译中…

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以上離れている。
  • 線分の端点は多角形の外部にある。
  • 多角形の連続する3頂点が一直線上に並ぶことはない。
翻译中…

すなわち、以下のような入力は与えられない。

翻译中…
  • A,B:多角形の頂点が線分上にある。
  • C:線分の端点が多角形の辺上にある。
  • D:多角形の辺と線分が重なる。
  • E:線分の端点が多角形の内部にある。
翻译中…

image

翻译中…

Output

翻译中…

板がいくつに切断されるかを出力せよ。出力の末尾には改行をつけること。

翻译中…

样例

Input #1
-2 0 2 0
4
1 1
-1 1
-1 -1
1 -1
Output #1
2
Input #2
-3 1 3 1
8
2 2
1 2
1 0
-1 0
-1 2
-2 2
-2 -1
2 -1
Output #2
3
题目信息
题号
abc016_4
时间限制
2 s
内存限制
256 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。