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.
Для отправки решений необходимо выполнить вход.
|