HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Linear Data Structures: Arrays > problem:


50913 - Manhattan Distance

Guest
• Review clarifications (1)

Section problems

• 50838 - Balanced Numbers
• 50851 - Repeated Numbers
• 51061 - The Longest Path
• 51083 - Grades Histogram
• 51084 - Reflect a matrix
• 51011 - Decoding the Path
• 50515 - Lines - Revisited
• 51088 - Number of letters
• 50913 - Manhattan Distance
• 51125 - Filling an Array 3
• 50824 - Sum of Group Maxes
• 50449 - The biggest result
• 51172 - The biggest Minute
• 51085 - xyx Divisible by k
• 51087 - Are they the same?
• 50442 - Polynomial Addition
• 51015 - Student Scholarships

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Manhattan Distance

Question: In a grid like shape, Manhattan distance is the sum of vertical and horizontal straight line distance. You will be given a point and the IDs and (x, y) coordinates of n other points. Then, you will be given the IDs of k points to process. Find the total Manhattan distance for all k points from the given point.

Input specification
You will be first given the (x, y) coordinate of a point. Then, you will be given two numbers: the number of all points (n) and the number of points to process (k). The following n lines will have three numbers ID and x, y coordinates of n points. In the last line, you will be given k numbers (IDs of k points to process) where 0 ≤ k ≤ n ≤ 10,000. and the coordinates are integers between -2e4 and 2e4.

Output specification:
Show one integer number: total Manhattan distance.

Sample Input I
5 8 8 4
3 9 10
8 1 6
11 8 2
15 10 8
17 9 7
18 7 3
21 4 6
22 8 1
3
8
15
18

 		Sample Output I
24

Explanation: The coordinate of the checkpoint is (5,8). There are 8 points given and k= 4. The following 8 lines, contain the ID and coordinates of 8 points. Then, we are given IDs of k points to process. Manhattan distance of:

  • point 3 is: 6 (9-5) + (10-8)
  • point 8 is: 6 (5-1) + (8-6)
  • point 15 is: 5
  • point 18 is: 7
Thus, the total distance is 24.



Для отправки решений необходимо выполнить вход.

www.contester.ru