Олимпиадный тренинг

Задача . A. Точки в пятимерном пространстве

Задача

Темы: геометрия математика Перебор *1700

Дано множество, состоящее из n точек в пятимерном пространстве. Точки пронумерованы от 1 до n. Никакие две точки не совпадают.

Назовем точку a плохой, если существуют две разные точки b и c из данного множества, не совпадающие с a, такие что угол между векторами $\text{[math]}$ и $\text{[math]}$ острый (строго меньше $\text{[math]}$ ). Иначе, назовем точку хорошей.

Угол между векторами $\text{[math]}$ и $\text{[math]}$ в пятимерном пространстве определен как $\text{[math]}$ , где $\text{[math]}$ — скалярное произведение и $\text{[math]}$ — длина вектора $\text{[math]}$ .

Выведите индексы всех хороших точек в порядке возрастания.

Входные данные

Первая строка входных данных содержит одно целое число n (1 ≤ n ≤ 10³) — количество точек.

Следующие n строк содержат по пять целых чисел a_i, b_i, c_i, d_i, e_i (|a_i|, |b_i|, |c_i|, |d_i|, |e_i| ≤ 10³) — координаты i-й точки. Все точки различны.

Выходные данные

Выведите число k — количество хороших точек.

В следующих k строках выведите индексы хороших точек в возрастающем порядке.

Примечание

В первом примере, первая точка образует угол ровно $\text{[math]}$ со всеми другими парами точек, поэтому она является хорошей.

Во втором примере точки лежат в плоскости cd и выглядят так:

$\text{[math]}$

Видно, что все углы острые, поэтому ни одна точка не является хорошей.

Примеры

№	Входные данные	Выходные данные
1	6 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1	1 1
2	3 0 0 1 2 0 0 0 9 2 0 0 0 5 9 0	0

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет