eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Meteorite

Meteorite

The Ministry of Emergency Situations (MES) was informed about the fall of a large meteorite that exploded in the atmosphere. The employees promptly examined the impact site and mapped the affected area in detail. It turned out that the affected area is bounded by a complex-shape polygon \textbf{M}. Unfortunately, there is a large city in this area. The boundaries of the city also represent a polygon, \textbf{G}. It is natural to expect that the major damage requiring the intervention of MES occurred at the intersection of polygons \textbf{M} and \textbf{G}. As an urgent measure, it was decided to calculate the number of separate parts of the city falling into the major damage zone. Note that none of the vertices of polygons \textbf{M} and \textbf{G} lies on the boundary of another polygon. Write a program that calculates the number of parts in the intersection of polygons \textbf{M} and \textbf{G}. \InputFile The first line contains integer \textbf{N}, the number of vertices in polygon \textbf{M}. The following \textbf{N} lines contain the coordinates of the vertices of \textbf{M} in the order of contour traversal. Coordinate values are separated with one or several space characters. The next line contains integer \textbf{K}, the number of vertices in \textbf{G}, and the following \textbf{K} lines contain the coordinates of its vertices. \textbf{3} ≤ \textbf{N}, \textbf{K} ≤ \textbf{300}. All coordinates are non-negative integers not exceeding \textbf{32000}. \OutputFile Output a single number -- the count of separate parts in the intersection of polygons \textbf{M} and \textbf{G}.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
4
0 0
3 5
7 1
4 3
3
2 2
2 0
7 2
Выходные данные #1
2
Источник 2013-2014 ACM Central Region of Russia Quarterfinal, Rybinsk 2013/10/17