問題一覧 > 教育的問題

No.2897 Distance Between Two Sets

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 65
作問者 : 👑 p-adic / テスター : 👑 binap
お気に入りにしたユーザー ProblemId : 10765 / 自分の提出
問題文最終更新日: 2026-10-23 08:16:19
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 447 オムニバス (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。