COCI 2016/2017 - Contest 3 - Meksikanac

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 3
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bạn có biết sự khác biệt giữa khách sạn và nhà nghỉ là gì không? Đúng vậy, chính là số lượng ruồi sống ở đó. Norman là chủ sở hữu của một trong những nhà nghỉ nổi tiếng ở Mỹ, nhưng mẹ anh cố thuyết phục anh biến nó thành khách sạn. Đó chính là lý do tại sao Norman lại được tặng một chiếc vỉ ruồi (một thiết bị diệt ruồi) có hình đa giác với ~K~ cạnh như món quà Giáng Sinh vào năm ~2016~.

Vì muốn đáp ứng yêu cầu của mẹ mình, Norman đến trước cửa sổ để xử lý ~N~ con ruồi ở đây. Vì Norman không muốn làm hại bất kì con ruồi nào, nên anh muốn biết có bao nhiêu cách để anh có thể đập vỉ ruồi vào cửa sổ mà không con ruồi nào bị thương.

Cửa sổ có dạng một hình chữ nhật với góc dưới bên trái của nó được đặt ở gốc tọa độ. Sau cú đánh của Norman vào cửa sổ, các đỉnh của đa giác phải nằm trên các tọa độ số nguyên và vỉ ruồi phải nằm hoàn toàn trong phạm vi của cửa sổ. Một con ruồi được coi là bị thương nếu nó nằm trên đỉnh, cạnh hoặc trong vỉ ruồi.

Input

  • Dòng đầu tiên chứa các số nguyên ~X_p~, ~Y_p~ và ~N~ ~(1 \le X_p, Y_p \le 500,\: 0 \le N \le X_p \cdot Y_p)~ lần lượt là tọa độ của góc trên bên phải của cửa sổ và số lượng ruồi trên cửa sổ.
  • ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~X~ và ~Y~ ~(0 < X < X_p,\: 0 < Y < Y_p)~, tọa độ của mỗi con ruồi trên cửa sổ.
  • Dòng tiếp theo chứa số nguyên ~K~ ~(3 \le K \le 10000)~, số đỉnh của vỉ ruồi.
  • ~K~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~X_i~, ~Y_i~ ~(-10^9 \le X_i, Y_i \le 10^9)~ là tọa độ đỉnh thứ ~i~ của vỉ ruồi. Các đỉnh của vỉ ruồi được in ra theo thứ tự các đường nối, vì vậy các đỉnh lân cận được nối với nhau bằng một đường thẳng.

Output

In ra số nguyên duy nhất là số cách để Norman đập vỉ ruồi vào cửa sổ mà không làm con ruồi nào bị thương.

Sample 1

Input
4 5 2
1 3
3 4
4
0 0
2 0
2 2
0 2
Output
4

Sample 2

Input
5 5 3
1 4
1 3
2 2
3
4 7
6 3
7 6
Output
3

Sample 3

Input
6 7 2
2 5
4 5
8
1 4
3 3
4 1
5 3
7 4
5 5
4 7
3 5
Output
1
Giải thích

Scoring

  • ~50~ test có ~1 \le X_p, Y_p \le 100~.
  • ~6~ test còn lại không có ràng buộc gì thêm.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.