CF2225E Covering Points with Circles

给定一个包含 $n$ 个整数坐标点的数组 $p$。这些点均匀分布在某个边平行于坐标轴的矩形内。 你需要放置若干个圆，使得满足以下条件： - 每个圆的半径均为 $r$，且圆心的坐标为整数； - 任意两个圆的交集面积为 $0$（圆可以相切但不能重叠）； - 至少有 $89\%$ 的点落在某个圆内部或圆的边界上（即落在圆内或圆上的点的数量不少于 $\frac{89n}{100}$）。 你并不知道数组 $p$ 中点分布所在的矩形，但除样例外，在所有测试数据中保证一个半径为 $r$ 的圆的面积不超过此矩形面积的 $\frac{1}{10}$。

第一行包含两个整数 $n$ 和 $r$（$4 \le n \le 10^4$，$10^2 \le r \le 10^3$）。 接下来 $n$ 行，每行包含两个整数 $p_x$ 和 $p_y$（$-10^5 \le p_x, p_y \le 10^5$）。 本题共 $40$ 个测试点。除题目中的样例外，每个测试点还满足： - 点的数量均为 $10^4$； - 所有点生成方式如下：首先在 $300$ 到 $10^5$ 之间随机选取一个整数 $x$，然后从矩形 $[-x, x] \times [-x, x]$ 中随机选取 $n$ 个不同的整数坐标点； - 半径为 $r$ 的圆面积不超过矩形 $[-x, x] \times [-x, x]$ 面积的 $\frac{1}{10}$； - 存在一组符合条件的圆覆盖方案。 本题不支持 hack。

第一行输出一个整数 $k$（$1 \le k \le n$）——圆的个数。接下来的 $k$ 行，每行输出两个整数 $x$ 和 $y$——第 $i$ 个圆心的坐标。你输出的圆心坐标的绝对值不超过 $2 \times 10^5$。 如果有多组解，输出任意一组即可。你不需要让圆的数量最小，但不得超过 $n$。

下图为第一个样例的其中一种覆盖方案：  由 ChatGPT 5 翻译