LCC/Moose '19 Contest 5 S4 - Manhattan

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 5.0s
Memory limit: 256M

Problem type

Reyno has recently moved to New York and is looking for housing in Manhattan. He wants to use this opportunity to introduce some healthy habits to his life, particularly going to the gym and cooking at home. To make this goal easier to achieve, he'd like to find a housing location that's as close as possible to both a grocery store and a gym.

Manhattan has N gyms and M grocery stores, each located at some intersection of a street Y (which go horizontally) and avenue X (which go vertically). The distance between two intersections is equal to the difference in their street numbers plus the difference in their avenue numbers.

Housing in Manhattan is plentiful, so Reyno can choose to live at any intersection. Help him find the minimum distance D such that there is an intersection that is at most D away from both a gym and a grocery store.

Input Specification

The input begins with an integer N (1 \le N, M \le 2 \times 10^5), the number of gyms and grocery stores, respectively.
The next N lines contain two integers X_i, Y_i (1 \le X_i, Y_i \le 10^9), the locations of the gyms.
The next M lines contain two integers X_i, Y_i (1 \le X_i, Y_i \le 10^9), the locations of the grocery stores.

An intersection may contain multiple gyms and grocery stores.

For at least 20 points, N, M \le 10^3.
For at least 40 points, X_i, Y_i \le 10^3.

Output Specification

Output a single integer, the minimum distance D.

Sample Input 1

1 1
3 3
4 4

Sample Output 1


Sample Input 2

2 2
1 1
1 2
3 4
3 3

Sample Output 2



There are no comments at the moment.