{"problem":{"name":"2nd Greatest Distance","description":{"content":"There are $N$ houses numbered $1$ through $N$ on a two-dimensional plane. House $i$ is at $(x_i, y_i)$. We use Chebyshev distance to calculate the distance between two houses. That is, the distance be","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc121_a"},"statements":[{"statement_type":"Markdown","content":"There are $N$ houses numbered $1$ through $N$ on a two-dimensional plane. House $i$ is at $(x_i, y_i)$.\nWe use Chebyshev distance to calculate the distance between two houses. That is, the distance between Houses $i$ and $j$ is $\\max(|x_i - x_j|, |y_i-y_j|)$.\nThere are $\\frac{N(N-1)}{2}$ pairs formed by two different houses. For each of these pairs, we will calculate the distance between the houses, and then we will sort these distances in **descending order** to get a sequence of length $\\frac{N(N-1)}{2}$. Find the second value from the beginning of this sequence.\n\n## Constraints\n\n*   All values in input are integers.\n*   $3 \\leq N \\leq 2 \\times 10^{5}$\n*   $-10^{9} \\leq x_i, y_i \\leq 10^{9}$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$x_{1}$ $y_{1}$\n$\\vdots$\n$x_{N}$ $y_{N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc121_a","tags":[],"sample_group":[["3\n0 0\n1 2\n4 0","3\n\n*   The distance between Houses $1$ and $2$ is $2$;\n*   The distance between Houses $1$ and $3$ is $4$;\n*   The distance between Houses $2$ and $3$ is $3$.\n*   By sorting these in descending order, we get $(4,3,2)$, where the second value from the beginning is $3$."],["4\n0 0\n0 0\n1 0\n0 1","1\n\n*   There may be multiple houses at the same coordinates."],["20\n407 361\n167 433\n756 388\n-551 -47\n306 -471\n36 928\n338 -355\n911 852\n288 70\n-961 -769\n-668 -386\n-690 -378\n182 -609\n-677 401\n-458 -112\n184 -131\n-243 888\n-163 471\n-11 997\n119 544","1766"]],"created_at":"2026-03-03 11:01:14"}}