给定一个数组 $$$p$$$,其中包含具有整数坐标的 $$$n$$$ 点。这些点均匀分布在某个边长与坐标轴平行的矩形内。
您需要放置几个圆圈,以便满足以下条件:
- 每个圆的半径等于$$$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$$$ 的圆的面积不超过矩形面积 $$$\frac{1}{10}$$$ $$$[-x, x] \times [-x, x]$$$;
- 存在一组满足问题条件的圆。
在此问题中,黑客被禁用。
输出
在第一行中,输出一个整数 $$$k$$$ ($$$1 \le k \le n$$$) — 圆的数量。在接下来的 $$$k$$$ 行中,输出两个整数 $$$x$$$ 和 $$$y$$$ — 第 $$$i$$$ 个圆的中心坐标。您输出的圆心坐标的绝对值不应超过 $$$2 \cdot 10^5$$$。
如果有多个解,则输出其中任意一个。您不需要最小化圆圈的数量,但不应超过 $$$n$$$。
示例
输入复制
4 1000 00 100100 0100 100
输出复制
1 70 70
注意
第一个样本的一种可能的覆盖物如图所示: