İstiqamətə Bənzərlik
Vektorların istiqamətləri var və iki vektor arasında bir bucaq yaranır.
Üç ölçülü vektorlar dəsti verildikdə, onların arasında ən kiçik bucaq yaradan cütü tapmaq sizin vəzifənizdir.
Giriş verilənləri
Giriş, verilənlər dəstlərinin ardıcıllığıdır. Hər bir verilənlər dəsti, bir dəst üç ölçülü vektorları göstərir, bunlardan bəziləri birbaşa verilənlər dəstində verilir, digərləri isə aşağıda təsvir olunan prosedurla yaradılır.
Hər bir verilənlər dəsti aşağıdakı kimi formatlanır:
m n S W
x_1 y_1 z_1
x_2 y_2 z_2
...
x_m y_m z_m
Birinci sətir dörd tam ədəd m, n, S və W ehtiva edir.
Tam ədəd m, komponentləri birbaşa verilənlər dəstində göstərilən vektorların sayıdır. İkinci sətirdən başlayaraq, m sətir m vektorun üç komponentini ehtiva edir. Hər bir i-ci sətir v_{i }= (x_i, y_i, z_i) vektorunu göstərir. Bütün vektor komponentləri 100-dən kiçik və ya bərabər olan müsbət tam ədədlərdir.
Tam ədəd n, aşağıdakı prosedurla yaradılan vektorların sayıdır.
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 üçün, dəstin i-ci vektoru bu prosedurla yaradılan üç komponent x[i], y[i] və z[i] malikdir.
Burada, S və W dəyərləri verilənlər dəstinin birinci sətrində verilən S və W parametrləridir. Sizə 1 ≤ S ≤ 10^9 və 1 ≤ W ≤ 10^9 olduğunu qəbul edə bilərsiniz.
Vektorların ümumi sayı 2 ≤ m+n ≤ 12×10^4 şərtini təmin edir. Qeyd edək ki, eyni vektor bir verilənlər dəstində iki və ya daha çox dəfə göstərilə bilər.
Dörd sıfırdan ibarət bir sətir girişin sonunu göstərir. Girişdəki bütün verilənlər dəstləri üçün m+n cəmi heç vaxt 16×10^5-dən çox olmur.
Çıxış verilənləri
Hər bir verilənlər dəsti üçün, göstərilən dəst arasında ən kiçik sıfırdan fərqli bucaq yaradan vektor cütünü çıxarın. Ən azı iki fərqli istiqamətə malik vektorun olduğu təmin edilir.
Vektorlar üç komponentləri ilə göstərilməlidir. v_a və v_b vektor cütü üçün çıxış bir sətirdə aşağıdakı kimi formatlanmalıdır:
x_a y_a z_a x_b y_b z_b
İki vektor (x_a, y_a, z_a) və (x_b, y_b, z_b) lüğət sırasına görə sıralanır, yəni, v_a < v_b əgər x_a < x_b, ya da əgər x_{a }= x_{b } və y_a < y_b, ya da əgər x_a = x_b, y_a = y_b və z_a < z_b. Bir vektor cütü çıxarıldıqda, bu sırada kiçik olan vektor əvvəl çıxarılmalıdır.
Əgər bir neçə cüt eyni ən kiçik bucağı yaradırsa, vektor cütləri arasında lüğət sırasına görə ən kiçik olan cüt çıxarılmalıdır. (v_i, v_j) cütü (v_k, v_l) cütündən kiçikdir əgər v_i < v_k, ya da əgər v_{i }= v_{k } və v_j < v_l.