Dağlara yürüş
Елена dostları ilə birlikdə dağlıq ərazilərə səyahət edir. Onların məqsədi düşərgə A-dan gözəl bir yer olan B-yə çatmaqdır.
Təəssüf ki, Elenada yüksəkliyə görə başgicəllənmə yaranır. Onun qrupuna elə bir marşrut tapmağa kömək edin ki, bu marşrutda maksimum hündürlük mümkün qədər az olsun.
Giriş məlumatları
Kvadrat bölgənin 10^6 * 10^6 ölçüsündə landşaftı haqqında tam məlumatı aşağıdakı formatda verilir. Birinci sətir landşaftdakı üçbucaqların sayını n (2 ≤ n ≤ 2000) göstərir. Sonrakı n sətirin hər biri üçbucağın koordinatlarını ehtiva edən doqquz tam ədəd x[i1], y[i1], z[i1], x[i2], y[i2], z[i2], x[i3], y[i3], z[i3] ehtiva edir. Bütün koordinatlar [0, 10^6] intervalına daxildir. Son iki sətirin hər biri düşərgə A və gözəl yer B-nin koordinatlarını ehtiva edən üç tam ədəd x[A], y[A], z[A] və x[B], y[B], z[B] ehtiva edir.
Verilən üçbucaqlar mütəşəkkil və davamlı bir landşaftı təsvir edir. Üçbucaqların XY müstəvisinə proyeksiyaları degenerasiya olunmur və kvadratı örtüşmədən doldurur. Bir üçbucağın zirvəsi heç vaxt başqa bir üçbucağın kənarında yerləşmir. A və B nöqtələri landşaftın səthinə aiddir və fərqlidir.
Çıxış məlumatları
A-dan B-yə qədər olan marşrutu ən az yüksək nöqtə ilə qırıq xətt şəklində çıxarın. Birinci sətirdə qırıq xəttin zirvələrinin sayını m çıxarın. Növbəti m sətirin hər birində qırıq xəttin zirvələrinin koordinatlarını ehtiva edən üç tam ədəd çıxarın: x[i], y[i] və z[i]. Zirvələri qırıq xəttin üzərindəki yerləşmə sırasına görə, A-dan B-yə qədər (bu iki nöqtə daxil olmaqla) çıxarın.
Qırıq xəttin zirvələrinin bütün koordinatları tam olmalıdır. Qırıq xəttin hər bir seqmenti giriş üçbucaqlarından birinə aid olmalıdır (mümkün halda üçbucağın tərəfinə). Qırıq xəttin zirvələrinin sayı 5n-dən çox olmamalıdır.