New Year's '17 P2 - Peter's Escape

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.8s
Memory limit: 256M

Authors:
Problem type

Peter the penguin is lost in an icy cave! Upon closer observation, he notices that he can represent the cave as an N \times M rectangle in the Cartesian plane. However, the ice is very slippery, and he can only stop and change directions when he slides onto one of O rock patches. In addition to this, he fears getting lost, so he will only move parallel to the axes.

Peter, much like any other sane penguin, is averse to sliding onto a rock patch, and as such, wishes to ask you a question: what is the minimum number of times he will do so while escaping the cave?

If there are two adjacent rock patches, (e.g. one at (2, 2) and another at (2, 3)), they are counted separately (i.e. he has slid over 2 rock patches).

Note: The cave is unbounded (i.e. there are no walls).

Input Specification

Line 1: two space separated integers, N and M (1 \le N, M \le 10^9).
Line 2: two space separated integers, X (1 \le X \le N) and Y (1 \le Y \le M), Peter's starting position.
Line 3: an integer, O (1 \le O \le 10^5).
Lines 4 \dots O+3: two space separated integers, x_i (1 \le x_i \le N) and y_i (1 \le y_i \le M), which represent the position of an obstacle. It is guaranteed that Peter's starting position will never be an obstacle.
Line O+4: an integer, E (1 \le E \le 10^5), the number of exits.
Lines O+5 \dots O+E+4, two integers, x_i (1 \le x_i \le N), and y_i (1 \le y_i \le M), the coordinates of an exit. It is guaranteed that Peter's starting position will never be an exit, and that no exit will contain an obstacle.

Output Specification

The output should consist of one integer, the minimum number of times Peter will slide over a rock patch while escaping the cave. If it is not possible to escape the cave, output -1 instead.

Subtasks

For 20\% of points, N, M \le 1\,000.

Sample Input

10 10
1 1
3
4 4
4 1
8 9
2
10 4
2 8

Sample Output

2

Comments


  • 0
    aeternalis1  commented on Aug. 30, 2017, 1:20 p.m.

    What's wrong with my code? I WA test case 3 of batch 1 and test case 6 of batch 2, but I have no idea why it doesn't work. I've made up a few test cases but it works for all of them. I'm fairly certain there's no issue with how I'm storing the adjacent rocks, so is there a problem with my binary search?


  • 1
    leonchen0613  commented on Jan. 1, 2017, 9:19 p.m.

    If the penguin is sliding towards two rock patches, one behind the other, will it stop when it gets to the first rock patch, or slide over both? If it stops at the first rock patch will it still count as sliding over two rock patches?


    • 0
      Kirito  commented on Jan. 1, 2017, 9:23 p.m.

      He will stop at the first one, and the patches are counted separately (i.e. 2 patches).


      • 1
        leonchen0613  commented on Jan. 1, 2017, 9:26 p.m.

        So when the penguin stops at the first rock patch (that is connected to another rock patch), you must say that the penguin slid over 2 rock patches?


        • 0
          r3mark  commented on Jan. 1, 2017, 10:54 p.m.

          No, you only count the number of individual squares which Peter slides on. If he were to stop at the first rock, it would count as 1. However, if he were to slide over both of them, then that would count as 2.


  • 0
    duckmoon  commented on Jan. 1, 2017, 2:32 p.m.

    Will the penguin stop if it hits a wall?


    • 0
      Kirito  commented on Jan. 1, 2017, 2:34 p.m.

      What walls are you referring to? The cave is unbounded (not surrounded by walls). He'll just slide off to infinity.


      • 1
        jimgao  commented on Jan. 1, 2017, 4:12 p.m.

        If so, wouldn't it be more appropriate to represent the cave with a rectangle that is infinitely large? What would be the point of M or N then?


        • 3
          r3mark  commented on Jan. 1, 2017, 4:17 p.m. edited

          For a more convenient representation of subtasks.


  • 0
    zscoder  commented on Jan. 1, 2017, 2:28 p.m.

    If a penguin slides over an exit, will it stop at the exit or overshoot the exit? (assuming no rocks are nearby)


    • 0
      imaxblue  commented on Jan. 1, 2017, 2:31 p.m. edit 3

      Yes, he will always stop at the exit