7. Построить квадрат

Не решаласьСредняя

Задано множество, состоящее из NN различных точек на плоскости. Координаты всех точек - целые числа. Определите, какое минимальное количество точек нужно добавить во множество, чтобы нашлось четыре точки, лежащие в вершинах квадрата.

Формат ввода

В первой строке вводится число NN (1N20001 \le N \le 2000) - количество точек.

В следующих NN строках вводится по два числа xix_i, yiy_i (108xi,yi108-10^8 \le x_i, y_i \le 10^8) - координаты точек.

Формат вывода

В первой строке выведите число KK - минимальное количество точек, которые нужно добавить во множество.

В следующих KK строках выведите координаты добавленных точек xix_i, yiy_i через пробел. Координаты должны быть целыми и не превышать 10910^9 по модулю.

Если решений несколько - выведите любое из них.

Ограничения

Ограничение времени

2 с

Ограничение памяти

256 МБ

Пример 1

Ввод
2
0 1
1 0
Вывод
2
0 0
1 1

Пример 2

Ввод
3
0 2
2 0
2 2
Вывод
1
0 0

Пример 3

Ввод
4
-1 1
1 1
-1 -1
1 -1
Вывод
0  

Теги

Нужно войти, чтобы отправить решение.Войти