Sfera
2011-ci ildə Xarkovda Qış Məktəbi Stanislav Pak tərəfindən təklif olunan "Sferalara toxunanlar" məsələsi ilə başladı. İlk gün tamamilə müəllifin məktəb illərindən bəri sevdiyi məkan geometriyasına həsr olunmuşdu, o zamanlar müəllif özü çox bəyəndiyi və aşağıda sizə də təklif olunan məkan həyat geometriya məsələsini həll edirdi:
"Sfera şəklində olan bir planetdə N şəhər var. Planetdə yalnız gündüz hərəkət etmək mümkündür və bir gündə D-dən çox məsafə qət etmək olmaz. Bir şəhərdən digərinə ən az gün sayında çatmaq lazımdır."
Giriş verilənləri
Giriş faylının əvvəlində tam ədəd N (1 ≤ N ≤ 1000) verilir. Sonra iki tam ədəd S_1 və S_2 (1 ≤ S_1, S_2 ≤ N, S_1 ≠ S_2) — aralarındakı yolu tapmaq lazım olan şəhərlərin nömrələri verilir. Sonra tam ədəd R (0 < R ≤ 10^11) — planetin radiusu verilir. Daha sonra tam ədəd D (0 < D ≤ 4·10^11) verilir. Növbəti N sıra şəhərlərin yerləşməsini G_1 T_1 G_2 T_2 şəklində göstərir, burada:
G_1 — enliyi göstərən həqiqi ədəd (0 ≤ G_1 ≤ 90);
T_1 — enlik simvolu: 'N' — şimal, 'S' — cənub;
G_2 — uzunluğu göstərən həqiqi ədəd (0 ≤ G_2 ≤ 180);
T_2 — uzunluq simvolu: 'E' — şərq, 'W' — qərb.
Çıxış verilənləri
Çıxış faylında səyahət üçün lazım olan minimal gün sayını və ya səyahət mümkün deyilsə -1 çıxarın.