Visible Black Areas
Contest: Educational Codeforces Round 42 (Rated for Div. 2)
Difficulty rating: 2800
Tags: data structures, dsu, geometry, trees

Petya has a polygon consisting of $$$n$$$ vertices. All sides of the Petya's polygon are parallel to the coordinate axes, and each two adjacent sides of the Petya's polygon are perpendicular. It is guaranteed that the polygon is simple, that is, it doesn't have self-intersections and self-touches. All internal area of the polygon (borders are not included) was painted in black color by Petya.

Also, Petya has a rectangular window, defined by its coordinates, through which he looks at the polygon. A rectangular window can not be moved. The sides of the rectangular window are parallel to the coordinate axes.

Blue color represents the border of a polygon, red color is the Petya's window. The answer in this case is 2.

Determine the number of black connected areas of Petya's polygon, which can be seen through the rectangular window.

Input format:
The first line contain four integers $$$x_1, y_1, x_2, y_2$$$ ($$$x_1 < x_2$$$, $$$y_2 < y_1$$$) — the coordinates of top-left and bottom-right corners of the rectangular window.

The second line contains a single integer $$$n$$$ ($$$4 \le n \le 15\,000$$$) — the number of vertices in Petya's polygon.

Each of the following $$$n$$$ lines contains two integers — the coordinates of vertices of the Petya's polygon in counterclockwise order. Guaranteed, that the given polygon satisfies the conditions described in the statement.

All coordinates of the rectangular window and all coordinates of the vertices of the polygon are non-negative and do not exceed $$$15\,000$$$.

Output format:
Print the number of black connected areas of Petya's polygon, which can be seen through the rectangular window.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The example corresponds to the picture above.

Example input:
5 7 16 3
16
0 0
18 0
18 6
16 6
16 1
10 1
10 4
7 4
7 2
2 2
2 6
12 6
12 12
10 12
10 8
0 8

Example output:
2

Editorial:
First, lets build a graph that represents only part of the polygon that is inside the window, as well as borders of the window. Do do this, for each segment of the polygon, find the intersection of that segment with the window, and, if it still is a segment with non-zero length, add it to the graph (add both endpoints as vertices and the segment itself as an edge). Next, add four corners of the window as vertices. Last, connect all the points on each of the four borders of the window with edges.
This way, we have a planar graph, and we can find faces in this graph which will represent all the connected areas inside the window, both belonging to the polygon and not. To count only those that belong to the polygon one can mark those oriented edges, that were created while intersecting polygon's segments with the window, as important. Only mark an edge if it is directed the same way as the corresponding segment of the polygon. This way, those faces of the graph that are to the left of important edges, are the ones belonging to the polygon.
But there is one bad case — when no segment of the polygon intersects with the window. It such case, the window is either entirely outside of the polygon, or entirely inside of it. To check this, find number of intersections of the polygon with a ray starting from inside of the window. If the number of intersections is even, the window is outside of the polygon. If it is odd, the window is outside.