Задача №111411. Сетка
Геральд потратил несколько часов, рисуя прямоугольную сетку на листе бумаги. Сначала он нарисовал несколько вертикальных линий на одинаковом расстоянии dx между ними. После этого он нарисовал несколько горизонтальных линий. Они также находились на одинаковом расстоянии dy друг от друга.
Пока Геральд отдыхал от трудов, его брат Майк пришел и нарисовал прямую линию на листе бумаги. Геральд разозлился и приказал Майку стереть все лишнее с бумаги.
Но Майк не воспринял всерьез слова брата и стер все. Но он заметил, что точки пересечения его линии с сеткой были достаточно жирными для того, чтобы быть заметными даже после стирания.
Помогите Геральду восстановить параметры исходной сетки.
Первая строка входного файла содержит одно целое число n — количество точек пересечения (3 ≤ n ≤ 100 000).
Каждая из следующих n строк содержит два целых числа xi, yi — координаты одной из точек пересечения. Координаты не превосходят 109 по абсолютной величине.
Все точки пересечения различны. Других общих точек, кроме описанных выше, у сетки и прямой Майка нет.
Выведите шесть целых чисел x1, x2, dx, y1, y2 и dy. Первые три числа описывают набор вертикальных прямых: минимальная x-координата вертикальной прямой, максимальная x-координата вертикальной прямой и расстояние между соседними вертикальными линиями ( - 109 ≤ x1 ≤ x2 ≤ 109; 0 < dx ≤ 2·109). Следующие три числа аналогично описывают набор горизонтальных линий ( - 109 ≤ y1 ≤ y2 ≤ 109; 0 < dy ≤ 2·109).
Гарантируется, что хотя бы одно решение существует.
4
1 1
5 3
3 2
9 5
1 9 4 2 5 3