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

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

Условие

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

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

Входной файл содержит числа N M x1 y1xN yN u1 w1uN wN, где xi yi - координаты вершин замка, ui vi - координаты вершин забора. Вершины перечислены в порядке обхода по часовой стрелке.

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

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

Ограничения

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

0.017s 0.005s 9