← 返回题目列表

Codeforces · 140/F

F. 新年雪花

中文机器翻译题面 查看原题

作为杰拉德......,换句话说,康斯坦丁在除夕夜为美丽的女士准备了一份不寻常的礼物。礼物是神奇的新年雪花,可以让任何梦想成真。

新年雪花由微小的冰晶组成,可以近似视为平面上的点。新年雪花的美妙之处在于它有一个对称中心。这是一个点,使得雪花的每个晶体都存在另一个晶体,相对于该点对称。其中一颗晶体可以直接放置在对称中心。

当康斯坦丁在数百万片雪花中挑选出一片同样对称、同样神奇的雪花,然后艰难地穿过雪堆来到情妇家的时候,当他屏息等待了好一会儿,美丽的女士打开门时,一些雪花晶体融化了,自然消失了。康斯坦丁确信这样的晶体不超过k个,因为他非常小心地处理雪花。现在他准备向美丽的女士展示纳米技术的全部力量并恢复雪花的对称性。

您将获得幸存雪花晶体的坐标,以纳米为单位。您的任务是确定原始对称中心的所有可能位置。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 10) — 相应地,幸存的雪花晶体的数量和熔化的晶体的最大数量。接下来的 n 行包含留下的晶体的坐标,其形式如下:“xi yi”。坐标为整数,绝对值不超过5·108。所有给出的点都是不同的。

输出

第一行包含一个整数 c — 可能的对称中心的数量。接下来的 c 行应包含中心的描述。每个对称中心由一对坐标“x y”描述,并用空格分隔。打印绝对误差不超过10 - 6 的坐标。可以以任何顺序打印对称中心。所有打印点应该不同。如果存在无限多个可能的对称中心,则打印单个数字“-1”。

示例

输入 #1

4 0
0 0
0 1
1 0
1 1

输出 #1

1
0.5 0.5

输入 #2

4 2
0 0
0 1
1 0
1 1

输出 #2

5
0.0 0.5
0.5 0.0
0.5 0.5
0.5 1.0
1.0 0.5

输入 #3

4 4
0 0
0 1
1 0
1 1

输出 #3

-1