D - 一刀両断 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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


入力

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

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:線分の端点が多角形の内部にある。

出力

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


入力例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