- Описание
- Отправленные решения
421. Построить квадрат
Задано множество, состоящее из $N$ различных точек на плоскости. Координаты всех точек $-$ целые числа. Определите, какое минимальное количество точек нужно добавить во множество, чтобы нашлось четыре точки, лежащие в вершинах квадрата.
Формат ввода
В первой строке вводится число $N$ ($1 \le N \le 2000$) $-$ количество точек.
В следующих $N$ строках вводится по два числа $x_i$, $y_i$ ($-10^8 \le x_i, y_i \le 10^8$) $-$ координаты точек.
Формат вывода
В первой строке выведите число $K$ $-$ минимальное количество точек, которые нужно добавить во множество.
В следующих $K$ строках выведите координаты добавленных точек $x_i$, $y_i$ через пробел. Координаты должны быть целыми и не превышать $10^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