Павел точно знает — завтра всегда лучше, чем вчера.
Он решил это доказать с помощью геометрии.
Для этого Павел рассмотрел n последовательных дней и каждому сопоставил точку на плоскости (xi, yi).
Он считает, что день i + 1 лучше дня i, если выполнено одно из двух условий:
- либо xi < xi + 1;
- либо xi = xi + 1, но yi < yi + 1.
Павел не уверен лишь в одном — правильно ли он выбрал систему координат для своих расчетов? Он уверен, что для поиска верной системы координат можно использовать только повороты и/или отражения.
Помогите Павлу — найдите любую прямоугольную (ортогональную) систему координат, в которой каждый следующий день будет лучше предыдущего.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество проанализированных Павлом дней.
В каждой из следующих n строк содержится по два целых числа xi и yi ( - 105 ≤ xi, yi ≤ 105) — точка, сопоставленная Павлом i-му дню.
В первой строке выведите YES, если такая прямоугольная система координат существует, и NO в противном случае.
Если искомая система координат существует, выведите ещё две строки.
Во второй строке выведите через пробел два целых числа Xx и Yx (|Xx|, |Yx| ≤ 109;|Xx| + |Yx| > 0) — координаты вектора, сонаправленного с осью Ox новой системы координат.
В третьей строке выведите через пробел два целых числа Xy и Yy (|Xy|, |Yy| ≤ 109;|Xy| + |Yy| > 0) — координаты вектора, сонаправленного с осью Oy новой системы координат.
Вектора (Xx, Yx) и (Xy, Yy) должны быть перпендикулярны между собой.
Если существует несколько вариантов ответа, выведите любой.
9
3 3
2 3
3 2
1 3
2 2
3 1
1 2
2 1
1 1
YES
-1 -1
1 -1
4
1 1
1 2
2 2
2 1
NO
1
100000 100000
YES
-100000 100000
-100000 -100000
2
0 0
0 0
NO
Первый тестовый пример
Сначала рассмотрим точки, сопоставленные дням, и найденные вектора в оригинальной системе координат:
Теперь покажем эти же точки в системе координат, основанной на найденных векторах:
Координаты точек после перехода в новую систему координат:
- (3, 3) — ( - 3, 0);
- (2, 3) — ( - 2.5, - 0.5);
- (3, 2) — ( - 2.5, 0.5);
- (1, 3) — ( - 2, - 1);
- (2, 2) — ( - 2, 0);
- (3, 1) — ( - 2, 1);
- (1, 2) — ( - 1.5, - 0.5);
- (2, 1) — ( - 1.5, 0.5);
- (1, 1) — ( - 1, 0).
Видно, что каждая следующая точка «лучше» предыдущей в новой системе координат.
