Задача D. Фотограф и замок ≡

Автор:	A. Klenin
Входной файл:	input.txt		Ограничение времени:	2 сек
Выходной файл:	output.txt		Ограничение памяти:	200 Мб

Условие

Старинный замок имеет в плане форму выпуклого N-угольника. Замок находится внутри участка, имеющего форму выпуклого M-угольника, огороженного высоким забором (замок не соприкасается с забором). Фотограф желает сделать несколько фотографий замка таким образом, чтобы каждая из стен была видна хотя бы на одной фотографии. Позиция для съёмки определяется точкой, находящейся внутри участка, но снаружи замка. Считается, что стена видна из данной позиции, если отрезок, соединяющий её с любой точкой стены, не пересекает других стен. Позиция не может лежать на прямой, содержащей стену. Требуется определить минимальное количество позиций для фотографии, которое придется сделать фотографу.

Формат входного файла

Входной файл содержит числа N M x₁ y₁ … x_N y_N u₁ w₁ … u_N w_N, где x_i y_i - координаты вершин замка, u_i v_i - координаты вершин забора. Вершины перечислены в порядке обхода по часовой стрелке.

Формат выходного файла

Выходной файл должен содержать единственное число — минимальное количество фотографий.

Ограничения

1 ≤ N, M ≤ 100. Все координаты представляют собой целые числа в диапазоне от 0 до 10000.

Примеры тестов

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	7 4 1 36 55 5 58 6 68 38 62 41 9 49 4 42 0 0 72 0 72 54 0 54	3

---