e-olymp 8528. Система глобальнейшего позиционирования

Задача

Недавно во Флатландии было решено создать Новейшую Систему Глобальнейшего Позиционирования. Поскольку страна занимает бесконечно большой участок плоскости, то вывод спутников очень затруднителен, поэтому было решено ограничиться наземным методом позиционирования.

Для этого во Флатландии было построено три радиовышки, не находящиеся на одной прямой. Объект, который хочет узнать свое местоположение, посылает вышкам сигнал. По силе сигнала, дошедшего до вышек, определяется расстояние между вышками и объектом.
Напишите программу, которая реализует последний компонент системы, который, получая координаты вышек и расстояния от объекта до каждой из них, находит координаты объекта.

Входные данные

В первой строке находятся три пары чисел $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$, $x_{3}$ и $y_{3}$  — координаты вышек. Во второй строке находятся три неотрицательных числа — расстояния до соответствующих вышек. Все входные числа целые и по модулю не превышают $50$.

Выходные данные

Если не существует такого местоположения объекта, что расстояния до вышек соответствовали бы данным, то выведите в единственное слово «Impossible». Иначе выведите два числа — координаты объекта с точностью до шести знаков после запятой.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 4 2 6 5 0
2 2 5
2.000000 4.000000
2 2 2 0 1 1 1
2.828427 1 1.4142135
0.000000 0.000000
3 -5 3 -3 3 -2 4
3 1 1
-2.000000 3.000000
4 0 0 2 1 2 -2
0.841722586 2 2
0.677124 -0.500000
5 0 0 10 0 5 6
7 7 1
Impossible

Код программы (Линейные вычисления)

Код программы (Ветвления)

Решение задачи

Для решения данной задачи нужно найти точку пересечения трёх окружностей, следовательно получаем систему из трёх уравнений окружностей, а именно:

[latex]\begin{cases}(x_{1} — x)^{2} + (y_{1} — y)^{2} = r_{1}^{2},\\(x_{2} — x)^{2} + (y_{2} — y)^{2} = r_{2}^{2}, \\(x_{3} — x)^{2} + (y_{3} — y)^{2} = r_{3}^{2};\end{cases}[/latex]

где $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$, $x_{3}$ и $y_{3}$  — координаты вышек, $r_{1}$, $r_{2}$ и $r_{3}$ — расстояния до соответствующих вышек, $x$ и $y$ — координаты объекта.

После применения формул сокращённого умножения многочленов, получим систему вида:

[latex]\begin{cases}x_1^2-2x_{1}x+x^{2}+y_1^2-2y_{1}y+y^{2}=r_1^2, & (1)\\x_2^2-2x_{2}x+x^{2}+y_2^2-2y_{2}y+y^{2}=r_2^2, & (2)\\x_3^2-2x_{3}x+x^{2}+y_3^2-2y_{3}y+y^{2}=r_3^2; & (3)\end{cases}[/latex]

Отнимем от первого уравнения второе и от  второго уравнения третье, получим:

[latex]\begin{cases}x_1^2-x_2^2-2x_{1}x+2x_{2}x+y_1^2-y_2^2-2y_{1}y+2y_{2}y=r_1^2-r_2^2, & (1)-(2)\\x_2^2-x_3^2-2x_{2}x+2x_{3}x+y_2^2-y_3^2-2y_{2}y+2y_{3}y=r_2^2-r_3^2; & (2)-(3)\end{cases}[/latex]

Далее выражаем $x$ и $y$:

[latex]\begin{cases}2y(y_{2}-y_{1})=r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2,\\2y(y_{3}-y_{2})=r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2;\end{cases}[/latex]

[latex]\begin{cases}2x(x_{2}-x_{1})=r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2,\\2x(x_{3}-x_{2})=r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2;\end{cases}[/latex]

[latex]\begin{cases}y=\frac{r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2}{2(y_{2}-y_{1})},\\y=\frac{r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2}{2(y_{3}-y_{2})};\end{cases}[/latex]

[latex]\begin{cases}x=\frac{r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2}{2(x_{2}-x_{1})},\\x=\frac{r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2}{2(x_{3}-x_{2})};\end{cases}[/latex]

Приравняем соответствующие координаты объекта, получим систему вида:

[latex]\begin{cases}\frac{r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2}{2(y_{2}-y_{1})}=\frac{r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2}{2(y_{3}-y_{2})},\\\frac{r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2}{2(x_{2}-x_{1})}=\frac{r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2}{2(x_{3}-x_{2})};\end{cases}[/latex]

Находим координаты объекта:

[latex]\begin{cases} \begin{split} 2(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2)= \\ =2(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2),\\2(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2)= \\ =2(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2); \end{split} \end{cases}[/latex]

[latex]\begin{cases} \begin{split} 2(y_{3}-y_{2})(2x_{1}x-2x_{2}x)-2(y_{2}-y_{1})(2x_{2}x-2x_{3}x) = \\ =2(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-\\-2(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2),\\2(x_{3}-x_{2})(2y_{1}y-2y_{2}y)-2(x_{2}-x_{1})(2y_{2}y-2y_{3}y)= \\ =2(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-\\-2(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2);\end{split}\end{cases}[/latex]

[latex]\begin{cases} \begin{split} 4x(y_{3}-y_{2})(x_{1}-x_{2})-4x(y_{2}-y_{1})(x_{2}-x_{3})= \\ =2(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-\\-2(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2),\\4y(x_{3}-x_{2})(y_{1}-y_{2})-4y(x_{2}-x_{1})(y_{2}-y_{3})= \\ =2(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-\\-2(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2);\end{split}\end{cases}[/latex]

[latex]\begin{cases}x=\frac{2((y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2))}{4((y_{3}-y_{2})(x_{1}-x_{2})-(y_{2}-y_{1})(x_{2}-x_{3}))},\\y=\frac{2((x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2))}{4((x_{3}-x_{2})(y_{1}-y_{2})-(x_{2}-x_{1})(y_{2}-y_{3}))};\end{cases}[/latex]

[latex]\begin{cases}x=\frac{(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2)}{2((y_{3}-y_{2})(x_{1}-x_{2})-(y_{2}-y_{1})(x_{2}-x_{3}))},\\y=\frac{(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2)}{2((x_{3}-x_{2})(y_{1}-y_{2})-(x_{2}-x_{1})(y_{2}-y_{3}))}.\end{cases}[/latex]

Далее проводим проверку на принадлежность  найденных  координат объекта одной из окружностей. Если найденные координаты принадлежат окружности, то выводим два числа — координаты объекта с точностью до шести знаков после запятой. Если найденные координаты не принадлежат окружности, это означает, что не существует такого местоположения объекта, тогда выводим единственное слово «Impossible».

Ссылки

Условие на e-olymp

Код программы (Линейные вычисления)

Код программы (Ветвления)

e-olymp 936. Формулы Крамера

Условие задачи
Решить систему двух линейных уравнений с двумя неизвестными по формулам Крамера. Система уравнений, приведенная во входных данных, имеет вид:
[latex]\begin{cases} 5x_1+8x_2=11 \\ -3x_1+6x_2=15 \end{cases}[/latex]

Входные данные
Первая строка содержит коэффициенты первого уравнения, а вторая строка содержит коэффициенты второго. Все входные числа разделены одним пробелом и не превышают по модулю $100$.

Выходные данные
Первый корень системы уравнений вывести в первой строке, а второй корень во второй строке с точностью до $0.001$.

Continue reading

e-olymp 2214. Функция 9

Задача

Дана функция, аргументы которой — произвольные натуральные числа

[latex]f(M,N)=\begin{cases} f(M-N,N), & \text{ npu } M>N \\ N, & \text{ npu } M=N \\ f(N-M,M) & \text{ npu } N>M \end{cases}[/latex]

Составить алгоритм (написать программу), вычисляющий значение функции.

Входные данные

Два натуральных числа [latex]n[/latex] и [latex]m[/latex] [latex](1 \le n, m \le 10^{18})[/latex].

Выходные данные

Искомое значение функции.

Тесты

Входные данные Выходные данные
[latex]6[/latex] [latex]3[/latex] [latex]3[/latex]
[latex]12[/latex] [latex]12[/latex] [latex]12[/latex]
[latex]126[/latex] [latex]98[/latex] [latex]98[/latex]
[latex]10329[/latex] [latex]1501[/latex] [latex]1501[/latex]
[latex]1008359[/latex] [latex]15113[/latex] [latex]15113[/latex]

Код программы

Решение задачи

Для решения задачи напишем функцию [latex]f[/latex]. Именно эта функция и будет считать искомое значение. Из условия задачи видим, что для решения потребуется рекурсия. Для этого, если остаток от деления одного натурального числа на другое не равен нулю, то мы снова возращаемся в функцию (в зависимости от того,
что больше [latex]m[/latex] или [latex]n[/latex]). Это будет продолжаться до тех пор, пока остаток от деления одного натурального числа на другое не будет равен нулю (как только $n\mod m = 0$ или $m\mod n = 0$, то функция возращает в переменную [latex]t[/latex] искомое значение). Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 16. Дракон

У каждой [latex]S[/latex]-ножки [latex]1[/latex] голова. Найти количество ног [latex]N[/latex] у [latex]K[/latex]-главого дракона, если у всех вместе [latex]A[/latex] голов и [latex]B[/latex] ног.

Входные данные

4 числа: [latex]S[/latex], [latex]K[/latex], [latex]A[/latex], [latex]B[/latex]. Все числа не превышают [latex]1000[/latex].

Выходные данные

Количество ног у дракона. Если входные данные противоречивы, вывести [latex]-1[/latex], в случае наличия нескольких решений – вывести любое из них.

Задача взята с сайта e-olymp.

Тесты

[latex]S[/latex] [latex]K[/latex] [latex]A[/latex] [latex]B[/latex] [latex]N[/latex] Комментарий
4 7 35 36 2 7 многоножек и 4 2-ногих дракона
10 3 10 34 8 1 многоножка и 3 8-ногих дракона
44 17 37 132 0 3  многоножки и 2 0 — ногих дракона
4 19 42 42 13 4 многоножки и 2 13 — ногих дракона
1 0 1 1 0 1 многоножка и 1 0 — ногий дракон
5 8 3 6 -1 Количество голов в сумме меньше чем у одного дракона
5 17 6 2 -1 Количество ног в сумме меньше чем у одной многоножки

Алгоритм

Для начала введем несколько дополнительных параметров. Обозначим количество имеющихся драконов через [latex]D[/latex], а количество многоножек как [latex]M[/latex]. Внесем имеющиеся данные в таблицу для удобства построения решения.

Дракон Многоножка
 Один Несколько  Одна  Несколько
 Голов Ног  Голов Ног Голов  Ног  Голов  Ног
[latex]K[/latex] [latex]N[/latex] [latex]KD[/latex] [latex]ND[/latex] [latex]1[/latex] [latex]S[/latex] [latex]M[/latex] [latex]SM[/latex]

Воспользуемся полученной таблицей и промоделируем сложившуюся ситуацию в виде системы уравнений:
[latex] \left\{\begin{matrix}
KD + M = A & \\
ND + SM = B &
\end{matrix}\right.[/latex]

Выразим из первого уравнения количество многоножек и подставим во второе уравнение:
[latex] \left\{\begin{matrix}
A — KD = M & \\
ND + S(A — KD) = B &
\end{matrix}\right.[/latex]

Раскрыв скобки, преобразуем выражение во втором уравнении:
[latex] \left\{\begin{matrix}

A — KD = M & \\
B — SA = D(N — SK) &
\end{matrix}\right.[/latex]

Теперь мы можем выразить количество драконов:
[latex] \left\{\begin{matrix}

A — KD = M & \\
\frac{B — SA}{N — SK} = D &
\end{matrix}\right.[/latex]

Учитывая тот факт, что мы работаем не просто с системой уравнений, а с величинами имеющими определенный логический смысл, проведем анализ полученного результата:

  1. [latex]D[/latex] — количество драконов, следовательно, это положительное целое число.
  2. Выполняя деление мы предполагаем, что [latex]N — SK[/latex] [latex]\neq[/latex] [latex]0[/latex]. Следует проверить имеет ли данный случай смысл и решение в контексте условия задачи.
    Вернемся к системе считая, что  [latex]N = SK[/latex]:
    [latex] \left\{\begin{matrix}A — KD = M & \\
    ND + S(A — KD) = B &
    \end{matrix}\right.[/latex][latex] \left\{\begin{matrix}A — KD = M & \\
    SKD + SA — SKD = B &
    \end{matrix}\right.[/latex][latex] \left\{\begin{matrix}A — KD = M & \\
    SA = B &
    \end{matrix}\right.[/latex]
    Приходим к выводу, что, при условии [latex]SA = B[/latex], задача гарантировано имеет решение вида [latex]N = SK[/latex].
  3. Теперь оценим знак полученного нами выражения:
    [latex]\frac{B — SA}{N — SK}[/latex] [latex]> 0[/latex] [latex] \Rightarrow[/latex] [latex](B — SA > 0[/latex] [latex]\wedge[/latex] [latex]N — SK > 0)[/latex]  [latex]\vee[/latex] [latex](B — SA < 0[/latex] [latex]\wedge[/latex] [latex]N — SK < 0)[/latex].
    Оценим значение [latex]B — SA [/latex]:
    [latex]B — SA = ND +SM — SA = ND +S(M — A) [/latex]
    [latex]M[/latex] — количество голов у одной многоножки, [latex]A[/latex] — общее количество голов [latex] \Rightarrow[/latex] [latex]M — A <= 0[/latex] , делаем вывод, что
    [latex]B — SA <= 0[/latex]  [latex]\forall[/latex] [latex]B, S, A[/latex] [latex] \Rightarrow[/latex] [latex]N — SK <= 0[/latex] [latex] \Rightarrow[/latex] [latex]N <= SK [/latex]

Анализ условия задачи окончен. Перейдем к реализации решения, принимая во внимание все  условия и ограничения полученные в процессе размышлений.
Запустим цикл от [latex]0[/latex] до [latex]SK[/latex] (выполнять цикл далее не имеет смысла, так как там не будет найдено ни одного решения), который перебирает количество ног дракона. Объединим все получившиеся ограничения:

  1. Прежде всего выполняем проверку для избежания деления на [latex]0[/latex]. (Условие проверки : [latex]SA = B[/latex]  [latex] \Rightarrow[/latex]  выводим результат [latex]N = SK [/latex] и заканчиваем работу программы).
  2. Иначе выполняем ряд последовательных проверок для текущего [latex]N[/latex] в цикле:
    • [latex]\frac{B — SA}{N — SK}[/latex] — целая величина. (Условие проверки : [latex]B — SA[/latex] делится нацело на [latex]N — SK[/latex])
    • Количество ног драконов не превышает общее количество ног минус количество ног одной многоножки (имеется хотя бы одна многоножка, которая имеет [latex]S[/latex] ног). (Условие проверки: [latex]B — S >= DN[/latex])
    • Количество голов драконов меньше чем общее количество голов (имеется хотя бы [latex]1[/latex] многоножка с [latex]1[/latex] головой). (Условие проверки: [latex]A > DK[/latex])

Как только выполняются все вышеописанные условия из пункта 2, выполняем вывод текущего количества ног дракона и заканчиваем работу программы, в противном случае выводим [latex]-1[/latex], так как данные противоречивы.

Примечание: в ходе решения выяснилось, что автор задачи предполагает существование 0 — ногих драконов, 0 — ногих многожек и т.д. Эти условия повлияли на вид некоторых неравенств.

Код программы:

Код программы
Засчитанное решение