TOURIST - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N attractions, the i-th is at (X_i, Y_i).
Find the minimum distance that needs to be traveled to reach any one attraction, starting from (A, B), under the Manhattan metric.

EXPLANATION:

Under the Manhattan metric, the distance between points (x_1, y_1) and (x_2, y_2) is equal to

|x_1 - x_2| + |y_1 - y_2|

This is because travel is independent along the x direction and y direction, so we add up the distances along each.

So, the distance from (A, B) to the i-th attraction, which is at (X_i, Y_i), equals

|A - X_i| + |B - Y_i|

The solution is hence to compute the distance to each attraction using this formula, then take the minimum of the distances.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, a, b = map(int, input().split())
    ans = 500
    for i in range(n):
        x, y = map(int, input().split())
        ans = min(ans, abs(a-x) + abs(b-y))
    print(ans)