Направленное сходство
Векторы имеют свои направления, и два вектора образуют угол между собой.
Дано множество трехмерных векторов, ваша задача — найти пару среди них, которая образует наименьший угол.
Входные данные
Входные данные состоят из нескольких наборов данных. Каждый набор данных определяет множество трехмерных векторов, некоторые из которых заданы непосредственно, а другие генерируются с помощью описанной ниже процедуры.
Каждый набор данных имеет следующий формат:
m n S W
x_1 y_1 z_1
x_2 y_2 z_2
...
x_m y_m z_m
Первая строка содержит четыре целых числа: m, n, S и W.
Целое число m — это количество векторов, чьи три компоненты указаны в наборе данных. Начиная со второй строки, m строк содержат три компоненты каждого из m векторов. i-я строка описывает вектор v_{i }= (x_i, y_i, z_i). Все компоненты векторов — положительные целые числа, не превышающие 100.
Целое число n — это количество векторов, генерируемых по следующей процедуре.
int g = S;
for (int i=m+1; i<=m+n; i++) {
x[i] = (g/7) %100 + 1;
y[i] = (g/700) %100 + 1;
z[i] = (g/70000)%100 + 1;
if( g%2 == 0 ) { g = (g/2); }
else { g = (g/2) ^ W; }
}
Для i = m+1, ..., m+n, i-й вектор v_i множества имеет три компоненты x[i], y[i] и z[i], сгенерированные этой процедурой.
Здесь значения S и W — это параметры S и W, указанные в первой строке набора данных. Вы можете предположить, что 1 ≤ S ≤ 10^9 и 1 ≤ W ≤ 10^9.
Общее количество векторов удовлетворяет условию 2 ≤ m+n ≤ 12×10^4. Обратите внимание, что один и тот же вектор может быть указан дважды или более в одном наборе данных.
Строка, содержащая четыре нуля, указывает на конец ввода. Общее количество m+n для всех наборов данных во входных данных никогда не превышает 16×10^5.
Выходные данные
Для каждого набора данных выведите пару векторов из указанного множества с наименьшим ненулевым углом между ними. Гарантируется, что существует как минимум два вектора с различными направлениями.
Векторы должны быть указаны их тремя компонентами. Вывод для пары векторов v_a и v_b должен быть отформатирован в строке следующим образом.
x_a y_a z_a x_b y_b z_b
Два вектора (x_a, y_a, z_a) и (x_b, y_b, z_b) упорядочены в лексикографическом порядке, то есть v_a < v_b, если x_a < x_b, или если x_{a }= x_{b } и y_a < y_b, или если x_a = x_b, y_a = y_b и z_a < z_b. Когда пара векторов выводится, меньший вектор в этом порядке должен быть выведен первым.
Если более одной пары образует одинаковый наименьший угол, должна быть выведена пара, которая является наименьшей среди них в лексикографическом порядке между парами векторов. Пара (v_i, v_j) меньше пары (v_k, v_l), если v_i < v_k, или если v_{i }= v_{k } и v_j < v_l.