Alyona and Triangles

题意翻译

### 题目描述 给定 n 个点，坐标都是整数， n 个点中任取 3 个点构成的三角形的面积都不超过 S 。 要求构造出一个三角形覆盖这 n 个点，并且面积不超过 4S 。该三角形的顶点可以不是这 n 个给定点。 ### 输入格式 第 1 行， 2 个整数 n ， S。 接下来 n 行，每行2个整数 x ， y ，表示点的横坐标和纵坐标。 保证有三分之一的点不共线。 ### 输出格式 每个顶点的坐标占一行，每个坐标对用空格隔开。 要求坐标为整数，且绝对值不超过 10^9 。 保证可以构造出三角形。 若有多个答案，任意输出一个。

题目描述

You are given $ n $ points with integer coordinates on the plane. Points are given in a way such that there is no triangle, formed by any three of these $ n $ points, which area exceeds $ S $ . Alyona tried to construct a triangle with integer coordinates, which contains all $ n $ points and which area doesn't exceed $ 4S $ , but, by obvious reason, had no success in that. Please help Alyona construct such triangle. Please note that vertices of resulting triangle are not necessarily chosen from $ n $ given points.

输入输出格式

输入格式

In the first line of the input two integers $ n $ and $ S $ ( $ 3<=n<=5000 $ , $ 1<=S<=10^{18} $ ) are given — the number of points given and the upper bound value of any triangle's area, formed by any three of given $ n $ points. The next $ n $ lines describes given points: $ i^{th} $ of them consists of two integers $ x_{i} $ and $ y_{i} $ $ (-10^{8}<=x_{i},y_{i}<=10^{8}) $ — coordinates of $ i^{th} $ point. It is guaranteed that there is at least one triple of points not lying on the same line.

输出格式

Print the coordinates of three points — vertices of a triangle which contains all $ n $ points and which area doesn't exceed $ 4S $ . Coordinates of every triangle's vertex should be printed on a separate line, every coordinate pair should be separated by a single space. Coordinates should be an integers not exceeding $ 10^{9} $ by absolute value. It is guaranteed that there is at least one desired triangle. If there is more than one answer, print any of them.

输入输出样例

输入样例 #1

4 1
0 0
1 0
0 1
1 1

输出样例 #1

-1 0
2 0
0 2

说明