LCC/Moose '20 Contest 1 J4 - Tracy and Cows

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Tracy the farmer is looking out at her field of cows. She has N brown cows and M black and white cows on a field of size 10^9 by 10^9. Today, Tracy wants to pick one brown cow and one black and white cow to milk. Her cows are very special - the lesser the distance she has to travel between them, the better the milk they produce will be. As such, she wants to pick two cows such that the distance she has to travel between them is as little as possible.

Tracy also has a very special tractor. Her tractor allows her to magically teleport between either two rows or two columns. She can choose which to teleport between, and she can only use this tractor once.

Given the locations of Tracy's cows, can you output the distance between the two cows she should milk to have the best possible milk?

Input Specification

The first line will contain two integers, N (1 \leq N \leq 10^5) and M (1 \leq M \leq 10^5), the number of brown cows and the number of black and white cows Tracy has, respectively.

The next N lines will contain two integers each, x_i (1 \leq x_i \leq 10^9) and y_i (1 \leq y_i \leq 10^9), the x and y position of one brown cow on the field.

The next M lines will contain two integers each, x_i (1 \leq x_i \leq 10^9) and y_i (1 \leq y_i \leq 10^9), the x and y position of one black and white cow on the field.

Output Specification

Output a single integer, the distance between the two cows Tracy should milk to have the best possible milk.

Subtasks

Subtask 1 [30%]

N \leq 10^2

M \leq 10^2

Subtask 2 [70%]

No additional constraints.

Sample Input 1

2 1
4 4
1000 2
1 1

Sample Output 1

1

Explanation for Sample 1

Tracy chooses to move between the second brown cow and first black and white cow. The x-distance between these two cows is 996 and the y-distance between these two cows is 1. Since she can use her tractor, she uses it to teleport between the two columns. Thus, she only has to travel a distance of 1 between the rows, making this the minimum distance.

Sample Input 2

2 2
1 1
1 2
4 4
5 5

Sample Output 2

2

Comments

There are no comments at the moment.