Входной файл: disast.in Выходной файл: disast.out Время на тест: 15 секунд Автор задачи: Н.П. Макарова (г. Гродно) Тесты к задаче:Скачать
Имеется карта района, на которой изображены различные географические объекты. Среди них – водоемы, имеющие форму непересекающихся многоугольников (с числом вершин не более 50). Многоугольник задается последовательным перечислением координат его вершин. Граница многоугольника представляет собой несамопересекающуюся ломаную.
Границу района стихийного бедствия можно изобразить на карте в виде несамопересекающейся замкнутой ломаной (с числом вершин не более 100).
Требуется определить число водоемов, полностью расположенных в зоне бедствия, число водоемов, расположенных вне зоны бедствия, и число водоемов, частично расположенных в зоне бедствия.
Границы водоемов, полностью находящихся в зоне бедствия, как и границы водоемов, находящихся вне зоны бедствия, могут иметь с границей зоны одну или более общих точек.
Ввод
В первой строке входного текстового файла DISAST.IN находится натуральное число N, задающее общее число водоемов (N<=50). В следующих строках следует описание водоемов. Для i-го водоема описание выглядит следующим образом: в отдельной строке вводится Ni – число вершин i-го водоема. Далее следуют Ni строк, в каждой из которых задаются разделенные одним пробелом координаты одной вершины многоугольника, образующего i-й водоем.
После описания водоемов в следующей строке находится натуральное число К<=100, задающее число звеньев ломаной, ограничивающей зону бедствия. Далее следуют К строк, в которых последовательно задаются разделенные одним пробелом координаты каждой вершины ломаной, ограничивающей зону бедствия.
Целочисленные значения всех координат X,Y удовлетворяют условию: 0<X<=1000, 0<Y<=1000.
Вывод
В единственной строке выходного текстового файла DISAST.OUT должны находиться разделенные единственным пробелом три числа К1, К2 и К3, где К1 – число водоемов, полностью расположенных в зоне бедствия, К2 – число водоемов, находящихся вне зоны бедствия, К3 – число водоемов, частично расположенных в зоне бедствия.
Пример
DISAST.IN
3
3
150 140
155 155
162 130
Число водоемов
Число вершин 1-го водоема
Координаты 1-го водоема
4
100 132
60 95
50 120
68 150
Число вершин 2-го водоема
Координаты 2-го водоема
3
90 100
120 82
107 70
Число вершин 3-го водоема
Координаты 3-го водоема
4
159 125
159 70
70 70
70 125
Число вершин зоны бедствия
Координаты зоны бедствия