2015 Mock CCC by Alex and Timothy

Problem J5: Royal Guard

Royal Guards protect the cities we live in. However, their numbers are limited and they have many zones in the city to protect, so they must constantly travel.

We will focus our attention on the patrol route of one Royal Guard throughout the course of a single day. If we take an aerial view of the city as a 2-dimensional coordinate plane, our particular Royal Guard always travels in straight lines parallel to the x- or y-axes. It is a well-known fact that Royal Guards travel by teleporting, but it's lesser known that they cannot teleport through massive buildings. Massive buildings are big, but compared to the city as a whole, they become mere points on the plane. If a massive building is on one of our Royal Guard's straight paths (even at the beginning or end of the path), he is forced to stop in front of it and walk around (or through) it while contemplating his job security and future career paths. Since these are unpleasant things to think of for a Royal Guard, he will have to mentally prepare himself at the beginning of the day as he learns of his patrol route of that day.

Out of pity for the Royal Guard and his monotonous daily life, you decide to help him write a program to compute the number of times he will ponder about his existence so he won't have to do it himself every day.

Input Format

The first line of input will have an integer N (1 ≤ N ≤ 100 000), the number of massive buildings.
The next N lines of input will each have the x- and y-coordinates of a single massive building. You may assume that the coordinates are pairwise distinct.
The (N + 1)th line will have an integer M (2 ≤ M ≤ 100 000), the number of turning points on the Royal Guard's route. The i-th path the Royal Guard walks is from the i-th turning point to the (i + 1)th turning point (for 1 ≤ i < M).
The next M lines will each contain the x- and y-coordinates of a turning point. It is guaranteed for the two turning points i and i + 1, exactly one of x_i = x_{i + 1} or y_i = y_{i + 1} will hold for all i such that 1 ≤ i < M.

All numbers in the input will be between 1 and 10⁹, inclusive.

Output Format

The first only line of output should contain a single integer – the total number of moments when the Royal Guard is deep in thought.
Note that the answer may be very large. In particular, it is not guaranteed to fit in a 32-bit integer.

Sample Input

4
2 2
2 3
3 2
3 3
5
1 2
4 2
3 2
3 5
3 1

Sample Output

7

Explanation of Sample

The massive buildings are arranged in a square shape. Note that paths can start or end on massive buildings. The following diagram depicts the royal guard's path, where each star represents a moment that he spends pondering his existence:

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Feb 18, 2015
Author: FatalEagle

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

What are the bounds on x and y?

The problem statement specifies this already.