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

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

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

Mif 17.16

Условие

Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

grph

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

Тестирование

Входные данные Выходные данные
1 0 0 Yes
2 -6 0 Yes
3 5.0 -2.0 Yes
4 -3.33 -5 No
5 0.12345 0.54321 No

Код

Решение

В основе заданной фигуры лежит круг с радиусом [latex]6[/latex] и центром в начале системы координат [latex](0, 0)[/latex], из которого исключена первая четверть. Таким образом, нам нужно удостовериться, что положение заданной точки одновременно удовлетворяет следующим условиям:

  • точка расположена в пределах круга, то есть сумма квадратов координат [latex]x^2+y^2[/latex] меньше или равна квадрату радиуса [latex]6^2=36[/latex];
  • хотя бы одна из координат точки [latex](x, y)[/latex] не превышает значения [latex]0[/latex] (другими словами, точка не лежит в первой четверти).

Если оба условия соблюдены, точка принадлежит фигуре. В противном же случае — нет. Такую проверку и последующий вывод ответа можно записать с помощью единственной тернарной операции:

Ссылки

Код программы на Ideone.com;

Уравнение окружности;

Список задач на ветвления.

Mif 17.5

Условие

Принадлежит ли точка [latex] \left( x,y \right) [/latex] фигуре на рисунке?

рисунок 17.5

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

Координаты точки [latex]\left(x,y\right)[/latex] на плоскости.

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

Если точка принадлежит фигуре, вывести «Принадлежит» (без кавычек), в противном случае — «Не принадлежит».

Задача взята отсюда.

Тесты

x y Вывод
1 1 -1 Принадлежит
2 0 0 Принадлежит
3 0 4 Принадлежит
4 5 0 Принадлежит
5 0 4.00001 Не принадлежит
6 -3 5 Не принадлежит
7 2 3 Принадлежит

Решение

Фигура в задаче представлена в виде двух четвертей окружностей, лежащих в I и IV четвертях с радиусами [latex] R1 [/latex] и [latex] R2 [/latex] , которые равны соответственно [latex] 4 [/latex] и [latex] 5 [/latex]. Центры окружностей находятся в начале координатных осей. Сразу после ввода координат точки выполняем проверку принадлежности фигуре, а именно: координата [latex]X\ge0[/latex] ? В случае отрицательного ответа программа выведет сообщение «Не принадлежит». Одновременно со знаком [latex]X[/latex] выполняется проверка с помощью формулы, полученной из уравнения окружности: [latex]{\left(x-{X}_{c}\right)}^{2}+{\left(y-{Y}_{c}\right)}^{2}\le{R}^{2}[/latex], где [latex]X_{c}[/latex] и [latex]Y_{c}[/latex] — координаты центра окружности. Если координаты точки проходят данную проверку для соответствующего радиуса, который зависит от знака [latex]Y[/latex], то точка принадлежит фигуре, в противном случае выведется сообщение «Не принадлежит».

Код

Код на сайте ideone.com находится здесь.