Условие
Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним«. Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений ([latex]1[/latex] – север, [latex]2[/latex] – северо-восток, [latex]3[/latex]– восток, [latex]4[/latex] – юго-восток, [latex]5[/latex] – юг, [latex]6[/latex] – юго-запад, [latex]7[/latex] – запад, [latex]8[/latex] – северо-запад) (см. рис). Длина шага в любом направлении равна 1. Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).
Вам необходимо написать программу, которая по указаниям пиратов определяет точку, где зарыт клад.
Входные данные
Первая строка входного файла содержит число [latex]N[/latex] – число указаний $(1 ≤ N≤ 40)$. Последующие [latex]N[/latex] строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.
Выходные данные
В выходной файл выведите координаты [latex]X[/latex] и [latex]Y[/latex] точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось [latex]Ox[/latex] направлена на восток, а ось [latex]Oy[/latex] – на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с точностью [latex]10^{-3}[/latex].
Тесты
| № | Ввод | Вывод |
| 1 | 6 1 3 3 1 1 1 3 3 5 2 7 1 |
3.000 2.000 |
| 2 | 1 8 10 |
-7.071 7.071 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <math.h> #include <iomanip> using namespace std; int main() { long long n, z, dir; long long x = 0, y = 0, ne = 0, se = 0; double dx, dy; cin >> n; while(n--) { cin >> dir >> z; switch (dir) { case 1: y += z; break; case 5: y -= z; break; case 3: x += z; break; case 7: x -= z; break; case 2: ne+= z; break; case 6: ne-= z; break; case 4: se+= z; break; case 8: se-= z; break; } } dx = x + (ne + se)*M_SQRT1_2; dy = y + (ne - se)*M_SQRT1_2; cout << fixed << setprecision(3) << dx << " " << dy; return 0; } |
Решение
Как видно из рисунка направление 1 совпадает с осью [latex]y[/latex], а 3 — с осью [latex]x[/latex]. Допустим, направление — переменная [latex]dir[/latex], а шаг-[latex]z[/latex]. Тогда, для направления 1 можно записать $y=z\cdot\cos((45^0)\cdot(dir — 1))$ , $x=z\cdot\sin((45^0)\cdot(dir-1)) $. Выражение $\cos((45^0)\cdot(1-1))=\cos(0^0)=1$ , то есть для 1 направления [latex]y=z[/latex], а выражение $\sin((45^0)\cdot(dir-1))=\sin((45^0)\cdot(1-1))=0 $. Следовательно, для направления 1 координаты [latex]y[/latex] и [latex]x[/latex] принимают значения: [latex]y=z[/latex], а [latex]x=0[/latex] .Рассмотрите значения приведенных выражений для всех направлений и увидим, что для всех направлений можно применить данные выражения для вычисления координат. А это позволяет сократить код программы.
