P7561

题意 给定 \(n\) 个点，求平面上，曼哈顿距离最近的 \(k\) 点对。 Sol 仔细想想就会发现，曼哈顿距离不好做最近 \(k\) 点对。 考虑转成切比雪夫距离。\(x' = x + y, y' = x - y\)。 二分答案，每次 \(check\) 一个 \(dis\)，询问距离小于 \( ......

# P7561[JOISC 2021 Day2] 道路の建設案 (Road Construction) 题解 ## 题目描述 JOI 国是一个 $x\times y$ 的二维平面，王国里有 $n$ 个城镇，分别编号为 $1, 2, \cdots, n \in [1,2.5 \times 10^5]$ ......