Сфера
Зимняя школа в Харькове 2011 началась задачкой "Касательные к сферам", предложенной Станиславом Паком. Первый день был полностью посвящён геометрии в пространстве, полюбившейся автору контеста ещё со школьных времён, когда он сам решал очень понравившуюся ему пространственную жизненную геометрическую задачку, предлагаемую ниже и вам:
"На планете, представляющей собой сферу, есть N городов. Передвигаться по планете можно только днём, и за один день можно пройти расстояние не больше D. Требуется за наименьшее количество дней добраться из одного города в другой."
Входные данные
В начале входного файла задано целое число N (1 ≤ N ≤ 1000). Затем заданы два целых числа S_1 и S_2 (1 ≤ S_1, S_2 ≤ N, S_1 ≠ S_2) — номера городов, путь между которыми необходимо найти. Затем задано целое число R (0 < R ≤ 10^11) — радиус планеты. Затем задано целое число D (0 < D ≤ 4·10^11). Следующие N строк задают расположение городов в виде G_1 T_1 G_2 T_2, где:
G_1 — вещественное число, задающее широту (0 ≤ G_1 ≤ 90);
T_1 — символ широты: 'N' — северная, 'S' — южная;
G_2 — вещественное число, задающее долготу (0 ≤ G_2 ≤ 180);
T_2 — символ долготы: 'E' — восточная, 'W' — западная.
Выходные данные
В выходной файл выведите минимальное число дней, необходимое для путешествия, или –1, если путешествие невозможно.