| Codeforces Round 358 (Div. 2) |
|---|
| Закончено |
Вам даны n точек на плоскости с целыми координатами. Известно, что площадь любого треугольника, образованного любыми тремя из данных n точек, не превосходит S.
Алёна пробовала построить треугольник с целыми координатами вершин, который содержит в себе все точки данного набора и площадь которого не превосходит 4S, но у нее ничего не получилось. Помогите Алёне построить такой треугольник. Заметьте, что точки, являющиеся вершинами искомого треугольника, могут не присутствовать в наборе.
В первой строке входных данных записаны два целых числа n и S (3 ≤ n ≤ 5000, 1 ≤ S ≤ 1018) — количество точек в наборе и ограничение сверху на площадь любого треугольника, составленного из любых трех точек набора, соответственно.
В следующих n строках заданы точки набора: в i-й из них содержатся два целых числа xi и yi ( - 108 ≤ xi, yi ≤ 108), разделенные пробелом, — координаты i-й точки набора.
Гарантируется, что среди n точек найдутся три, не лежащие на одной прямой.
Выведите координаты трех точек, являющихся вершинами треугольника, который содержит в себе все точки данного набора и площадь которого не превосходит 4S.
Координаты каждой вершины треугольника выводите в отдельной строке, разделяя каждую пару координат пробелом. Координаты должны быть целыми числами, не превосходящими 109 по модулю.
Гарантируется, что искомый треугольник существует. Если ответов несколько, выведите любой.
4 1
0 0
1 0
0 1
1 1
-1 0
2 0
0 2
Картинка к примеру из условия:
