No.2897 Distance Between Two Sets
Note
The execution time limit for this problem is 3500[ms].
(Added on 2024-09-21) The title of this section was corrected from "Problem Statement" to "Note". The content of the problem itself has not changed.
Problem Statement
You are given a positive integer $N$ and a set $S$ consisting of $N$ distinct points in the $xy$-plane, and a positive integer $M$ and a set $T$ consisting of $M$ distinct points in the $xy$-plane.
The distance $d(s,t)$ between an element $s = (x,y)$ of $S$ and an element $t = (z,w)$ of $T$ is defined as the $\ell^1$ distance (Manhattan distance)
$\displaystyle |x-z| + |y-w| $
Furthermore, the distance $D(S,T)$ between $S$ and $T$ is defined as the minimum value of $d(s,t)$ as $s$ and $t$ range over all elements of $S$ and $T$ respectively:
$\displaystyle \min_{(s,t) \in S \times T} d(s,t) $
Find $D(S,T)$.
Input
Number the elements of $S$ by the positive integers $n$ not exceeding $N$ and write them as $s_n = (x_n,y_n)$, and number the elements of $T$ by the positive integers $m$ not exceeding $M$ and write them as $t_m = (z_m,w_m)$.
Then the input is given from standard input in $2 + N + M$ lines in the following format:
- Line $1$ contains $N$.
- For each positive integer $n$ not exceeding $N$, line $1 + n$ contains $x_n, y_n$ separated by a single-byte space.
- Line $2 + N$ contains $M$.
- For each positive integer $m$ not exceeding $M$, line $2 + N + m$ contains $z_m, w_m$ separated by a single-byte space.
$N$ $x_1$ $y_1$ $\vdots$ $x_N$ $y_N$ $M$ $z_1$ $w_1$ $\vdots$ $z_M$ $w_M$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 2 \times 10^5$.
- For any positive integer $n$ not exceeding $N$,
- $x_n$ is an integer satisfying $0 \leq x_n < 10^3$.
- $y_n$ is an integer satisfying $0 \leq y_n < 10^3$.
- For any positive integers $n_0, n_1$ not exceeding $N$, if $n_0 \neq n_1$ then $s_{n_0} \neq s_{n_1}$.
- $M$ is an integer satisfying $1 \leq M \leq 2 \times 10^5$.
- For any positive integer $m$ not exceeding $M$,
- $z_m$ is an integer satisfying $0 \leq z_m < 10^3$.
- $w_m$ is an integer satisfying $0 \leq w_m < 10^3$.
- For any positive integers $m_0, m_1$ not exceeding $M$, if $m_0 \neq m_1$ then $t_{m_0} \neq t_{m_1}$.
Output
Output $D(S,T)$ on $1$ line.
Sample
Sample 1
Input
1 0 0 1 1 1
Output
2
We have $S = \{(0,0)\}$ and $T = \{(1,1)\}$. Since each of them has only $1$ element, the distance $D(S,T)$ between $S$ and $T$ coincides with the distance between their only elements:
$\displaystyle d((0,0),(1,1)) = |0-1| + |0-1| = 2 $
This is the answer.
Sample 2
Input
2 0 1 1 0 2 1 0 1 1
As in this case, $S$ and $T$ may have common points.
Output
0
We have $S = \{(0,1),(1,0)\}$ and $T = \{(1,0),(1,1)\}$. Each of them has $2$ elements, and
$\displaystyle \begin{array}{rcl} d((0,1),(1,0)) & = & |0-1| + |1-0| = 2 \\ d((0,1),(1,1)) & = & |0-1| + |1-1| = 1 \\ d((1,0),(1,0)) & = & |1-1| + |0-0| = 0 \\ d((1,0),(1,1)) & = & |1-1| + |0-1| = 1 \end{array} $
so the distance $D(S,T)$ between $S$ and $T$ is the minimum of these, $0$.
Sample 3
Input
3 0 0 1 0 2 0 2 0 1 1 1
Output
1
We have $S = \{(0,0),(1,0),(2,0)\}$ and $T = \{(0,1),(1,1)\}$.
$\displaystyle \begin{array}{rcl} d((0,0),(0,1)) & = & |0-0| + |0-1| = 1 \\ d((0,0),(1,1)) & = & |0-1| + |0-1| = 2 \\ d((1,0),(0,1)) & = & |1-0| + |0-1| = 2 \\ d((1,0),(1,1)) & = & |1-1| + |0-1| = 1 \\ d((2,0),(0,1)) & = & |2-0| + |0-1| = 3 \\ d((2,0),(1,1)) & = & |2-1| + |0-1| = 2 \end{array} $
so the distance $D(S,T)$ between $S$ and $T$ is the minimum of these, $1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。