Метеорит#6195

Метеорит

1 секунда

64 мегабайти

Дуже складна

Міністерство з надзвичайних ситуацій (МНС) отримало повідомлення про падіння великого метеорита, який вибухнув в атмосфері. Співробітники швидко обстежили місце падіння та ретельно нанесли на карту уражену територію.

З'ясувалося, що уражена територія має форму багатокутника $M$ . На жаль, у цій зоні розташоване велике місто, межі якого також утворюють багатокутник $G$ . Очікується, що основні пошкодження, які потребують втручання МНС, відбулися на перетині багатокутників $M$ та $G$ .

Як терміновий захід було вирішено підрахувати кількість окремих частин міста, що потрапляють у зону основних пошкоджень. Важливо зазначити, що жодна з вершин багатокутників $M$ та $G$ не лежить на межі іншого багатокутника.

Напишіть програму, яка обчислює кількість частин у перетині багатокутників $M$ та $G$ .

Вхідні дані

Перший рядок містить ціле число $N$ , яке визначає кількість вершин у багатокутнику $M$ . Наступні $N$ рядків містять координати вершин $M$ у порядку обходу контуру. Значення координат розділені одним або кількома пробілами.

Наступний рядок містить ціле число $K$ , яке визначає кількість вершин у $G$ , і наступні $K$ рядків містять координати його вершин.

$3 \leq N, K \leq 300$ 3 \le N, K \le 300. Усі координати — невід'ємні цілі числа, що не перевищують $32000$ .

Вихідні дані

Виведіть одне число — кількість окремих частин у перетині багатокутників $M$ та $G$ .

Приклади

Приклад 1