Задача
Недавно во Флатландии было решено создать Новейшую Систему Глобальнейшего Позиционирования. Поскольку страна занимает бесконечно большой участок плоскости, то вывод спутников очень затруднителен, поэтому было решено ограничиться наземным методом позиционирования.
Для этого во Флатландии было построено три радиовышки, не находящиеся на одной прямой. Объект, который хочет узнать свое местоположение, посылает вышкам сигнал. По силе сигнала, дошедшего до вышек, определяется расстояние между вышками и объектом.
Напишите программу, которая реализует последний компонент системы, который, получая координаты вышек и расстояния от объекта до каждой из них, находит координаты объекта.
Входные данные
В первой строке находятся три пары чисел $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 |
Код программы (Линейные вычисления)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <iomanip> #include <cmath> using namespace std; int main() { double eps = 1e-6; double x1, y1, x2, y2, x3, y3, r1, r2, r3, x, y; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> r1 >> r2 >> r3; x = ((y2 - y1) * (r2 * r2 - r3 * r3 - y2 * y2 + y3 * y3 - x2 * x2 + x3 * x3) - (y3 - y2) * (r1 * r1 - r2 * r2 - y1 * y1 + y2 * y2 - x1 * x1 + x2 * x2)) / (2 * ((y3 - y2) * (x1 - x2) - (y2 - y1) * (x2 - x3))); y = ((x2 - x1) * (r2 * r2 - r3 * r3 - x2 * x2 + x3 * x3 - y2 * y2 + y3 * y3) - (x3 - x2) * (r1 * r1 - r2 * r2 - x1 * x1 + x2 * x2 - y1 * y1 + y2 * y2)) / (2 * ((x3 - x2) * (y1 - y2) - (x2 - x1) * (y2 - y3))); ((abs((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) - r1 * r1) < eps) && (cout << fixed << setprecision (6) << x << " " << y << endl)) || ((abs((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) - r1 * r1) >= eps) && (cout << "Impossible" << endl)); return 0; } |
Код программы (Ветвления)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> #include <iomanip> #include <cmath> using namespace std; int main() { double eps = 1e-6; double x1, y1, x2, y2, x3, y3, r1, r2, r3, x, y; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> r1 >> r2 >> r3; x = ((y2 - y1) * (r2 * r2 - r3 * r3 - y2 * y2 + y3 * y3 - x2 * x2 + x3 * x3) - (y3 - y2) * (r1 * r1 - r2 * r2 - y1 * y1 + y2 * y2 - x1 * x1 + x2 * x2)) / (2 * ((y3 - y2) * (x1 - x2) - (y2 - y1) * (x2 - x3))); y = ((x2 - x1) * (r2 * r2 - r3 * r3 - x2 * x2 + x3 * x3 - y2 * y2 + y3 * y3) - (x3 - x2) * (r1 * r1 - r2 * r2 - x1 * x1 + x2 * x2 - y1 * y1 + y2 * y2)) / (2 * ((x3 - x2) * (y1 - y2) - (x2 - x1) * (y2 - y3))); if (abs((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) - r1 * r1) < eps) cout << fixed << setprecision (6) << x << " " << y << endl; else cout << "Impossible" << endl; return 0; } |
Решение задачи
Для решения данной задачи нужно найти точку пересечения трёх окружностей, следовательно получаем систему из трёх уравнений окружностей, а именно:
[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».
Ссылки
Код программы (Линейные вычисления)
Для отправки комментария необходимо войти на сайт.