Mock CCC '15 J5 - Royal Guard

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type
2015 Mock CCC by Alex and Timothy

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 encounter a building and ponder about his existence so he won't have to do it himself every day.

Input Specification

The first line of input will have an integer N (1 \le N \le 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 can assume that the coordinates are pairwise distinct.
The (N+1)^\text{th} line will have an integer M (2 \le M \le 100\,000), the number of turning points on the Royal Guard's route. The i^\text{th} path the Royal Guard walks is from the i^\text{th} turning point to the (i+1)^\text{th} turning point (1 \le 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 (1 \le i < M).
All numbers in the input will be between 1 and 10^9, inclusive.

Output Specification

The first and only line of output should be the total number of times that the Royal Guard encounters a building and falls deep into thought.
Note that the answer may be very large. In particular, it is not guaranteed to fit in a 32-bit integer.

Sample Input

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

Sample Output



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:


  • 0
    aeternalis1  commented on July 27, 2017, 11:02 a.m.

    Problem with my method or with my optimization?

    I keep TLE'ing test cases after 9. Is there a faster method to complete this problem or is it just because of how I wrote my code?

    • 0
      Kirito  commented on July 27, 2017, 2:51 p.m.

      Your code's time complexity is \mathcal O(N \times M), which is too slow.