14746번 - Closest Pair 다국어

Given two sets P and Q of finitely many points in the plane, a closest pair of P and Q is a pair (p, q) of points p ∈ P and q ∈ Q such that the distance between p and q is the minimum among all pairs (p′, q′) with p′ ∈ P and q′ ∈ Q.

Specifically, in this problem, by the distance between two points a and b in the plane, we mean:

d(a, b) = |x_a - x_b| + |y_a - y_b|

where x_a and y_a denote the x- and y-coordinates of point a, and x_b and y_b denote the x- and y-coordinates of point b. Then, a pair (p, q) with p ∈ P and q ∈ Q is a closest pair of P and Q if and only if the following holds:

d(p, q) = min{ d(p′, q′) | p′ ∈ P and q′ ∈ Q}

Given two sets P and Q, write a program that computes the distance between a closest pair of P and Q and the number of distinct closest pairs of P and Q.

Note that you can assume the following on the input points in P and Q:

1. All the points in P lie on the horizontal line y = c₁ while all the points in Q lie on the horizontal line y = c₂ for some integers c₁ and c₂.
2. No two input points in P have the same coordinates; no two input points in Q have the same coordinates.

Your program is to read from standard input. The input consists of four lines. The first line contains two integers, n (1 ≤ n ≤ 500,000) and m (1 ≤ m ≤ 500,000), where n is the number of points in set P and m is the number of points in set Q. In the second line, two integers c₁ and c₂ (-10⁸ ≤ c₁, c₂ ≤ 10⁸) are given in order, separated by a single space. In the third line, n distinct integers between -10⁸ and 10⁸, inclusively, are given, separated by a single space, that are the x-coordinates of the points in set P, while their y- coordinates are all the same as c₁. In the fourth line, m distinct integers between -10⁸ and 10⁸, inclusively, are given, separated by a single space, that are the x-coordinates of the points in set Q, while their y- coordinates are all the same as c₂.

Your program is to write to standard output. Print exactly one line for the input. The line should contain two integers, separated by a single space, that represent the distance between a closest pair of P and Q and the number of closest pairs of P and Q in this order.