Метеорит
Министерство по чрезвычайным ситуациям (МЧС) получило сообщение о падении крупного метеорита, который взорвался в атмосфере. Спасатели оперативно обследовали место падения и тщательно нанесли на карту пострадавшую область.
Выяснилось, что пострадавшая территория ограничена многоугольником сложной формы M. К сожалению, в этой зоне расположен крупный город. Границы города также образуют многоугольник, обозначенный как G. Ожидается, что основные повреждения, требующие вмешательства МЧС, произошли на пересечении многоугольников M и G.
В качестве срочной меры было решено подсчитать количество отдельных частей города, попавших в зону основных повреждений. Обратите внимание, что ни одна из вершин многоугольников M и G не лежит на границе другого многоугольника.
Напишите программу, которая вычисляет количество частей в пересечении многоугольников M и G.
Входные данные
Первая строка содержит целое число N, обозначающее количество вершин в многоугольнике M. Следующие N строк содержат координаты вершин M в порядке обхода. Значения координат разделены одним или несколькими пробелами.
Следующая строка содержит целое число K, обозначающее количество вершин в многоугольнике G, и следующие K строк содержат координаты его вершин.
3 ≤ N, K ≤ 300. Все координаты — неотрицательные целые числа, не превышающие 32000.
Выходные данные
Выведите одно число — количество отдельных частей в пересечении многоугольников M и G.