Напрямкова Схожість
Вектори мають свої напрямки, і два вектори утворюють кут між собою.
Дано набір тривимірних векторів, ваше завдання — знайти пару серед них, яка утворює найменший кут.
Вхідні дані
Вхідні дані складаються з кількох наборів. Кожен набір визначає тривимірні вектори, деякі з яких задані безпосередньо, а інші генеруються за процедурою, описаною нижче.
Кожен набір даних має такий формат:
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.