CF2225E.Covering Points with Circles

You are given an array $p$ containing $n$ points with integer coordinates. These points are uniformly distributed inside some rectangle whose sides are parallel to the coordinate axes.

You need to place several circles so that the following conditions hold:

• the radius of each circle is equal to $r$, and its center has integer coordinates;
• for every pair of circles, the area of their intersection is $0$ (but the circles may touch);
• at least $89$% of all points lie inside some circle or on the boundary of some circle (in other words, the number of points lying inside the circles or on their boundaries is at least $\frac{89n}{100}$).

The rectangle in which the points from array $p$ are distributed is unknown to you, but in all tests except for the example it is guaranteed that the area of one circle of radius $r$ does not exceed $\frac{1}{10}$ of the area of this rectangle.

给你一个包含 $n$ 个整数坐标点的数组 $p$。这些点均匀分布在某个边与坐标轴平行的矩形内部。

你需要放置若干个圆，使得满足以下条件：

• 每个圆的半径均为 $r$，且其圆心坐标为整数；
• 任意两个圆的交集面积为 $0$（但两圆可以相切）；
• 至少 $89\%$ 的所有点位于某个圆的内部或边界上（即：位于圆内或圆边界上的点的数量至少为 $\frac{89n}{100}$）。

数组 $p$ 中的点所分布的矩形对你而言是未知的；但在除样例外的所有测试中，保证半径为 $r$ 的单个圆的面积不超过该矩形面积的 $\frac{1}{10}$。

The first line contains two integers $n$ and $r$ ($4 \le n \le 10^4$, $10^2 \le r \le 10^3$).

The next $n$ lines each contain two integers $p_{x}$ and $p_{y}$ ($-10^5 \le p_x, p_y \le 10^5$).

There are $40$ tests in this problem. For each test except the example from the statement, the following constraints hold:

• the number of points is $10^4$;
• all points are generated as follows: first, some integer $x$ from $300$ to $10^5$ is chosen; after that, $n$ distinct integer points are chosen uniformly at random in the rectangle $[-x, x] \times [-x, x]$;
• the area of a circle of radius $r$ does not exceed $\frac{1}{10}$ of the area of the rectangle $[-x, x] \times [-x, x]$;
• there exists a set of circles satisfying the conditions of the problem.

Hacks are disabled in this problem.

第一行包含两个整数 $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 功能。

In the first line, output one integer $k$ ($1 \le k \le n$) — the number of circles. In each of the next $k$ lines, output two integers $x$ and $y$ — the coordinates of the center of the $i$-th circle. The coordinates of centers of the circles you output should not exceed $2 \cdot 10^5$ by absolute value.

If there are multiple solutions, output any of them. You do not need to minimize the number of circles, but it should not exceed $n$.

第一行输出一个整数 $k$（$1 \le k \le n$）—— 圆的个数。接下来的 $k$ 行中，每行输出两个整数 $x$ 和 $y$ —— 第 $i$ 个圆的圆心坐标。你所输出的各圆圆心坐标的绝对值不得超过 $2 \cdot 10^5$。

若存在多种解法，输出任意一种即可。你无需最小化圆的个数，但其值不得超过 $n$。

One possible covering for the first sample is shown in the figure:

第一个样例的一种可能覆盖方式如图所示：