매칭

기하 매칭 문제에서는 두 기하 도형 $A$와 $B$가 주어진다. 목표는 $B$를 변환하여 변환된 $B$가 $A$에 최대한 가까워지도록 만드는 것이다. $A$와 변환된 $B$ 사이의 거리는 미리 정해진 거리 함수로 측정하며, 이 거리를 최소화하는 변환을 구한다.

이 문제는 더 단순한 변형이다. $A$와 $B$는 평면 위의 유한한 점 집합이고, $B$에 허용되는 변환은 평행이동뿐이다. 벡터 $v = (v_x, v_y)$만큼 평행이동한 $B$는 다음과 같다.

$B + v = \{(x + v_x, y + v_y) \mid (x, y) \in B\}.$

임의의 벡터 $v$에 대해 거리 함수 $f(v)$는 $A$와 $B + v$의 모든 점을 사이에 두는 두 평행선의 수직 거리 중 가능한 가장 작은 값이다. $f(v)$를 최소화하는 벡터 $v$를 찾고, $f(v)$의 값을 출력한다.

$A = \{(0,0), (0,100)\}$과 $B = \{(23,56), (123,56)\}$를 보자. 그림 (a)에서 $A$의 점은 빨간색, $B$의 점은 파란색이다. $v = (-73, -6)$일 때, 그림 (b)는 $A$와 $B + v$를 보여 주며, 두 평행선의 거리는 $d = 50\sqrt{2}$이다. 이 두 직선은 $A$와 $B + v$의 모든 점을 사이에 두고 있으며 가능한 가장 작은 수직 거리를 가진다. 따라서 $f(v) = d$이다. 이는 모든 벡터에 걸쳐 $f$의 최솟값이므로, $v = (-73, -6)$은 최적의 평행이동이다.

첫 줄에 두 정수 $n$ ($1 \le n \le 200{,}000$)과 $m$ ($1 \le m \le 200{,}000$)이 주어진다. $n$은 $A$의 점 개수이고, $m$은 $B$의 점 개수이다. 이어지는 $n$개의 줄에는 $A$의 각 점의 좌표가 공백으로 구분된 두 정수로 주어진다. 그다음 $m$개의 줄에는 같은 형식으로 $B$의 각 점의 좌표가 주어진다. 모든 좌표는 $-10^6$ 이상 $10^6$ 이하이다. 같은 좌표의 점이 $A$나 $B$에 여러 번 나올 수 있다.

최적의 벡터 $v$에 대한 $f(v)$ 값인 실수 $z$를 한 줄에 출력한다. 출력은 정수부, 소수점, 소수부로 이루어지며, $z$는 $f(v) - 10^{-6} < z < f(v) + 10^{-6}$을 만족해야 한다.