P7561 [JOISC 2021] Road Construction Plan (Road Construction) (Day2).

10s, 2048M.

The Kingdom of JOI is a $x \times y$ two-dimensional plane. There are $n$ towns in the kingdom, numbered $1, 2, \cdots, n$, and the **coordinates** of town $i$ are $(x_i, y_i)$. In the Kingdom of JOI, there is a plan to build roads connecting two towns (hereinafter referred to as a **“road construction project”**). There will be $k$ roads. Connecting two different towns $a$ and $b$ costs $|x_a − x_b| + |y_a − y_b|$ yen. If there is already a road connecting $c$ and $d$, then there is no need and it is not allowed to build another road connecting $d$ and $c$, because they are the same. You need to manage this “road construction project”. To calculate the costs, you need to figure out the costs required to connect some towns. Among these $\dfrac{n\cdot(n-1)}{2}$ possible roads, you want to know the costs of the cheapest $k$ roads. Given the coordinates of the towns and $k$, compute how much money is needed for the cheapest $k$ roads.

The input consists of $n+1$ lines. The first line contains two positive integers $n, k$. $n$ is the number of towns, and the meaning of $k$ is described in the **Description** section. Each of the next lines $2 \sim n+1$ contains two integers $x_i$ and $y_i$ ($1 \le i \le n$), representing the coordinates of town $i$.

Output $k$ lines. On line $k$, output one integer representing the cost in yen of the $k$-th cheapest road.

#### Sample #1 Explanation There are $\dfrac{3 \times 2}{2} = 3$ possible choices. - Town $1 \to$ town $2$: $|(-1)-0|+|0-2| = 3$ yen. - Town $1 \to$ town $3$: $|(-1)-0|+|0-0| = 1$ yen. - Town $2 \to$ town $3$: $|0-0|+|2-0| = 2$ yen. Sorting them gives $1, 2, 3$, so the output is $1$ and $2$. This sample satisfies Subtasks $1, 4, 5, 6$. #### Sample #2 Explanation There are $\dfrac{5 \times 4}{2} = 10$ possible choices. After sorting, the costs are $2, 2, 3, 3, 3, 3, 4, 4, 4, 4$. This sample satisfies Subtasks $1, 4, 5, 6$. #### Sample #3 Explanation This sample satisfies Subtasks $1, 2, 4, 5, 6$. #### Sample #4 Explanation This sample satisfies Subtasks $1, 4, 5, 6$. #### Constraints and Notes **This problem uses subtask scoring.** | Subtask | Score Percentage | $n$ | $k$ | $y_i$ | | :----: | :----: | :----: | :----: | :----: | | $1$ | $5\%$ | $\le 10^3$ | / | / | | $2$ | $6\%$ | / | / | $=0$ | | $3$ | $7\%$ | / | $=1$ | / | | $4$ | $20\%$ | / | $\le 10$ | / | | $5$ | $27\%$ | / | $\le 10 ^ 5$ | / | | $6$ | $35\%$ | / | / | / | **Note: A slash means there is no special restriction.** For $100\%$ of the testdata: - $2 \le n \le 2.5 \times 10^5$. - $1 \le k \le \min(2.5 \times 10^5,\ \dfrac{n\cdot(n-1)}{2}$). - $-10^9 \le x_i, y_i \le 10^9$, and $1 \le i \le n$. - $(x_i, y_i)\not = (x_j, y_j)$ for $1 \le i < j \le n$. #### Notes This problem is translated from [The 20th Japanese Olympiad in Informatics 2020/2021 Spring Training Camp -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Contest 2 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day2/2021-sp-d2-notice.pdf) [T2 Japanese statement](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day2/road_construction.pdf). Translated by ChatGPT 5