Задача D. Метеорит
Задачу добавил: alef
Успешно сдано решений: 7
На полигон НИИЧАВО был доставлен огромный камень (по некоторым предположениям, метеорит). О камне было известно лишь то, что все, кто подходил к нему достаточно близко, стремились его расколоть. Впрочем, на камне имелись уже небольшие трещины, возможно, рукотворного происхождения. Потому было решено разделить его на несколько частей, соблюдая, конечно, все меры предосторожности. На полигоне собралось практически все руководство НИИЧАВО и большинство сотрудников. И когда все уже было готово к началу испытания, камень неожиданно раскололся сам, и в результате серии микровзрывов его многочисленные осколки оказались разбросанными по всему полигону. Кто-то из особо наблюдательных первым заметил, что осколки меняют цвет и, сверх того, форму. Медлить было нельзя, и все сотрудники, которые были на это способны, попытались образовать защитный контур. Ваша задача – выяснить, сколько осколков метеорита оказалось вне этого контура.
Формат входного файла input.txt
Первая строка содержит два целых числа M (1 <= M <= 1000) и N (1 <= N <= 100) через пробел. M – количество осколков метеорита, N – количество сотрудников НИИЧАВО, способных участвовать в образовании защитного контура. Следующие M строк содержат по два целых числа Xj и Yj через пробел – координаты осколка № j (1 <= j <= M), –10000 <= Xj, Yj <=10000. Следующие N строк содержат по два целых числа XCq и YCq через пробел – координаты сотрудника № q (1 <= q <= N), участвующего в образовании защитного контура (–10000 <= XCq, YCq <= 10000). При образовании контура сотрудник № q взаимодействует с сотрудниками № (q+1) и № (q–1), сотрудник № 1 и сотрудник № N своим взаимодействием замыкают контур. Гарантируется, что в контуре отсутствуют самопересечения.
Формат выходного файла output.txt
Первая строка содержит целое число – число осколков метеорита, которое оказалось вне защитного контура.
Пример входного файла
2 1
1 1
1 2
1 2
Пример выходного файла
1