HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Volumes > Array and Matrices > problem:


50913 - Manhattan Distance

Guest
• Review clarifications (1)

Volume problems

• 50749 - Min Distance
• 50915 - Trip to Korca
• 50985 - Books Waiting
• 50927 - Health Expenses
• 50983 - Course Selection
• 50745 - Bitonic Sequence
• 50789 - Number of Cities
• 50987 - Very Looong Queue
• 50913 - Manhattan Distance
• 50981 - Top popular m-students
• 50729 - Max number in 2D array
• 50743 - Total Scholarships Discount
• 51083 - Grades Histogram
• 51024 - Total Stock Price
• 51008 - Sum of Regional Maxes
• 51014 - Nine Men's Morris game
• Word Puzzle

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