SHARE
TWEET

Untitled

a guest Jul 20th, 2017 134 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. **********************************************************************
  2.  
  3. Problem 2: Cows on Ice [Jelle van den Hooff, 2010]
  4.  
  5. Bessie is ice skating on a large frozen lake modelled as a 2-dimensional
  6. grid with coordinates in the range -1,000,000,000..1,000,000,000.
  7. N (1 <= N <= 20,000) of the lake's grid cells contain rocks
  8. (conveniently numbered 1..N). The other cells contain slippery ice.
  9.  
  10. Since Bessie is not a very good skater, she traverses the lake's
  11. cells by pushing herself away from her current position near a rock
  12. and sliding continuously in the same direction until she hits another
  13. rock (stopping in the square before she hits the rock, of course).
  14. Never good with complicated angles, Bessie can push herself only
  15. straight north, east, south, or west. She can't push herself through
  16. the rock, of course, and thus generally has only three possible
  17. directions to move.
  18.  
  19. Sliding is not without risks. Bessie must hit a rock or might end
  20. up sliding for a very long time. She must aim her pushes carefully.
  21.  
  22. Consider the situation depicted below; Bessie wants to get to
  23. location (x=5,y=1), which is east of her current location (. = ice,
  24. * = rock, B = Bessie, G = goal). If she slides directly to the east,
  25. she will slide past the location since she can stop only by
  26. encountering a rock head on. One way to get to (5,1) is the following:
  27.  
  28.    (a)              (b)             (c)              (d)
  29. 4 .....*.         .....*.         .....*.          .....*.
  30. 3 ..*....  slide  ..*....  slide  ..*....   slide  ..*....
  31. 2 ......*  north  ..B...*  east   .....B*   south  ......*
  32. 1 .*B..G. ------> .*...G. ------> .*...G.  ------> .*...B.
  33. 0 *....*.         *....*.         *....*.          *....*.
  34.   0123456
  35.  
  36. Bessie could slide north, east, or south in situation (a), but only
  37. north has a rock for stopping. For situation (b), she can slide
  38. only east for the same reason.
  39.  
  40. For the input, rock i is located at cell X_i,Y_i (-1,000,000,000
  41. <= X_i <= 1,000,000,000; -1,000,000,000 <= Y_i <= 1,000,000,000),
  42. and no two rocks occupy the same position. Bessie starts at Bx,By
  43. (which is next to a rock) (-1,000,000,000 <= Bx <= 1,000,000,000;
  44. -1,000,000,000 <= By <= 1,000,000,000). Bessie's goal is Gx,Gy
  45. (-1,000,000,000 <= Gx <= 1,000,000,000; -1,000,000,000 <= Gy <=
  46. 1,000,000,000). Bessie can always reach the goal one way or another.
  47.  
  48. Bessie doesn't mind sliding. However, pushing herself away from a
  49. rock is very tiring. To prepare her, FJ would like to know the
  50. minimum number of pushes Bessie needs to do.
  51.  
  52. PROBLEM NAME: ice
  53.  
  54. INPUT FORMAT:
  55.  
  56. * Line 1: Five space separated integers: N, Bx, By, Gx, and Gy
  57.  
  58. * Lines 2..N+1: Line i+1 describes a rock location with space
  59.         separated integers: X_i and Y_i
  60.  
  61. SAMPLE INPUT (file ice.in):
  62.  
  63. 6 2 1 5 1
  64. 5 4
  65. 2 3
  66. 1 1
  67. 6 2
  68. 5 0
  69. 0 0
  70.  
  71. OUTPUT FORMAT:
  72.  
  73. * Line 1: A single integer that is the minimum number of pushes for
  74.         Bessie to get to her goal
  75.  
  76. SAMPLE OUTPUT (file ice.out):
  77.  
  78. 3
  79.  
  80. **********************************************************************
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top