← 返回题目列表

Codeforces · 682/E

E. 阿廖娜和三角形

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

给定平面上具有整数坐标的 n 个点。点的给出方式使得这 n 个点中的任意三个点形成的三角形的面积都不超过 S。

Alyona 试图构造一个具有整数坐标的三角形,其中包含所有 n 个点,并且其面积不超过 4S,但由于显而易见的原因,没有成功。请帮助阿廖娜构造这样的三角形。请注意,生成的三角形的顶点不一定是从 n 个给定点中选择的。

输入

在输入的第一行中,给出了两个整数 n 和 S (3 ≤ n ≤ 5000, 1 ≤ S ≤ 1018) — 给定的点数以及由给定 n 个点中的任意三个形成的任何三角形面积的上限值。

接下来的 n 行描述给定的点:第 i 个点由两个整数 xi 和 yi (- 108 ≤ xi, yi ≤ 108) 组成 - 第 i 个点的坐标。

保证至少有一个三重点不在同一条线上。

输出

打印三个点的坐标 - 包含所有 n 个点且面积不超过 4S 的三角形的顶点。

每个三角形顶点的坐标应打印在单独的行上,每个坐标对应以单个空格分隔。坐标应为绝对值不超过 109 的整数。

保证至少有一个所需的三角形。如果有多个答案,请打印其中任何一个。

示例

输入 #1

4 1
0 0
1 0
0 1
1 1

输出 #1

-1 0
2 0
0 2