HTTP Request Redirection

Problem Description

The developers at Amazon are working on fixing a bug where an HTTP request is being redirected to different servers. There are n servers placed on an infinite 2D plane, each defined by their x and y coordinates. The coordinates of the i^th server are represented by locations[i].

Additionally, there are q redirect records that specify the directions in which the requests were redirected. The i^th redirection is represented by redirectRecords[i].

The request is being redirected from one server (a, b) to another server in one of the following four ways, where Z is an arbitrary positive integer:

Direction 1: (a, b) → (a + Z, b + Z)
Direction 2: (a, b) → (a + Z, b - Z)
Direction 3: (a, b) → (a - Z, b + Z)
Direction 4: (a, b) → (a - Z, b - Z)

The request is redirected to the nearest server present in the given direction. The below rules are followed when the request is re-directed:

The request is always re-directed towards the nearest server (in terms of distance, which corresponds to the smallest positive integer Z) in the given direction.
If no unvisited server exists in that direction, the redirection is deemed invalid and is skipped. The request remains at the current server.
Additionally, the request cannot be redirected to any server it has previously visited. The starting server is marked as visited at the start of the re-direction process itself.

Given a matrix locations representing the positions of n servers and an array redirectRecords of size q indicating the directions for redirecting the request, the task is to determine the final coordinates of the server to which the request is redirected and return them as an array [x, y].

Note: The request starts at the first server's coordinates, i.e., from locations[0].

Example 1

Input:
locations = [[3, 4], [1, 2], [7, 8], [5, 6]]
redirectRecords = [1, 4]

Output: [1, 2]

Explanation:

The request initially starts at the first server located at locations[0], i.e., at coordinates (3, 4). Mark this server as visited.
The first redirection is redirectRecords[0] = 1 (Direction 1). From the current server (3, 4), we look for unvisited servers of the form (3 + Z, 4 + Z).
- There are 2 unvisited servers in this direction: (5, 6) (which corresponds to Z=2) and (7, 8) (which corresponds to Z=4).
- Because (5, 6) is closer (has a smaller Z), the request is redirected to (5, 6).
The request will now start from server (5, 6). Mark this server as visited.
The second redirection is redirectRecords[1] = 4 (Direction 4). From the current server (5, 6), we look for unvisited servers of the form (5 - Z, 6 - Z).
- There is only 1 unvisited server in this direction: (1, 2) (which corresponds to Z=4).
- The request is redirected to server at (1, 2).
Since there are no more redirection requests to process, the final location is (1, 2). Thus, we return [1, 2].

Example 2

Input:
locations = [[0, 0], [2, 1], [3, 3], [4, 2]]
redirectRecords = [4, 1, 4, 2]

Output: [4, 2]

Explanation:

Start at locations[0] = (0, 0). Visited: {(0, 0)}.
redirectRecords[0] = 4. From (0, 0), look for an unvisited server of the form (0-Z, 0-Z). No server matches. The redirection is skipped. Current location remains (0, 0).
redirectRecords[1] = 1. From (0, 0), look for an unvisited server of the form (0+Z, 0+Z). Server (3, 3) matches with Z=3. Redirect to (3, 3). Visited: {(0, 0), (3, 3)}.
redirectRecords[2] = 4. From (3, 3), look for an unvisited server of the form (3-Z, 3-Z). Server (0, 0) matches with Z=3, but it's already visited. No other unvisited server matches. The redirection is skipped. Current location remains (3, 3).
redirectRecords[3] = 2. From (3, 3), look for an unvisited server of the form (3+Z, 3-Z). Server (4, 2) matches with Z=1. Redirect to (4, 2).
All requests processed. The final location is (4, 2).

Function Signature

Complete the function determineLocation in the editor. It has the following parameters:

int locations[n][2]: the location of the servers, where each row consists of [x, y] coordinates.
int redirectRecords[q]: the direction in which the request is redirected.

Returns

int[2]: the coordinates of the final location of the request in the form [x, y].

C++ function signature:

vector<int> determineLocation(vector<vector<int>> locations, vector<int> redirectRecords);

Constraints

1 ≤ n ≤ 10⁵
1 ≤ q ≤ 10⁵
0 ≤ locations[i][0], locations[i][1] ≤ 10⁹
1 ≤ redirectRecords[i] ≤ 4