Задача J. Точки на n-мерном параллелепипеде

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Пусть имеется набор из m точек n-мерного евклидова пространства, заданных своими декартовыми координатами: (x1i, x2i, …, xni), где нижний индекс обозначает номер точки, а верхний — номер координаты.

Требуется определить, существует ли n-мерный параллелепипед (со сторонами, параллельными осям координат), на границе которого лежат указанные точки.

Формат входного файла

В начале входного файла "input.txt" хранятся два натуральных числа: m и n.

Далее следует m строк, содержащих координаты точек исходного множества: (x1i, x2i, …, xni).

Формат выходного файла

Выходной файл "output.txt" должен содержать одно из следующих значений:

1 — если такой параллелепипед существует;

0 — в противном случае.

Ограничения

Все входные значения являются целыми десятичными числами.

 − 104 < xki < 104, 0 < n ≤ 10, 0 < m ≤ 5 ⋅ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
 6 3
-3056 -5013 -4706
 6423  9875  1023
-3056 -5013  1023
 6423 -5013 -4706
-3056  9875 -4706
 6423 -5013  1023
1
2
 5 2
-3170 -1400
 4950 -1400
-3170  7030
  150  3500
 4950  7030
0

0.129s 0.016s 15