Задача
В пустой прямоугольной комнате размерами [latex]A \times B \times C[/latex] (длина, ширина, высота) на пол упала уснувшая муха. Паук, находившийся на одной из стен, или на полу комнаты, начал двигаться к ней по кратчайшему пути.
На какое расстояние он при этом переместится?
Входные данные
В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке — координаты мухи [latex]X_1[/latex], [latex]Y_1[/latex] и паука [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex].
Все входные данные — целые числа, не превышающие 500.
Выходные данные
Единственное число — расстояние, на которое переместится паук, вычисленное с точностью до 2-х знаков после запятой.
Тесты
Входные данные | Выходные данные |
$3$ $4$ $8$
$0$ $0$ $3$ $4$ $0$ |
$5.00$ |
$2$ $2$ $8$
$1$ $1$ $2$ $1$ $4$ |
$5.00$ |
$6$ $4$ $3$
$5$ $1$ $0$ $2$ $1$ |
$6.08$ |
$30$ $60$ $27$
$13$ $21$ $8$ $0$ $17$ |
$38.33$ |
$40$ $40$ $40$
$10$ $5$ $8$ $40$ $37$ |
$72.03$ |
Код программы
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 |
#include <iostream> #include <iomanip> #include <cmath> using namespace std; double distance (double X1,double X2,double Y1,double Y2) { return (sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2))); } int main() { cout.precision(2); double A, B, C; cin>>A>>B>>C; double X2, Y2, X1, Y1, Z2; cin>>X1>>Y1; cin>>X2>>Y2>>Z2; double s=250000000; if (Z2==0) s=distance (X1,X2,Y1,Y2);//"floor" case else { if (X2==0) {X2=-Z2; s=distance (X1,X2,Y1,Y2);}//"left wall" case if (X2==A) {X2=A+Z2; s=distance (X1,X2,Y1,Y2);}//"right wall" case if (Y2==0) {Y2=-Z2; s=min(s, distance (X1,X2,Y1,Y2));}//"near wall" case if (Y2==B) {Y2=B+Z2; s=min(s, distance (X1,X2,Y1,Y2));}//"distant wall" case } cout<<fixed<<s; return 0; } |
Решение задачи
Суть решения задачи заключается в переходе от трехмерного пространства комнаты к двумерному с помощью «развёртки» комнаты на координатную плоскость.
Переведя координаты паука в комнате в его новые координаты в двумерном пространстве, все, что нам остается сделать — вычислить кратчайшее расстояние между двумя точками на плоскости с помощью функции [latex]distance[/latex].
В простейшем случае, если паук находится на полу комнаты, т.е. его координата [latex]Z_2[/latex] нулевая, координаты паука [latex]X_2[/latex] и [latex]Y_2[/latex] в точности описывают его положение в координатной плоскости развёртки, и преобразовывать их не требуется.
В противном случае отдельно рассматриваем варианты расположения паука на каждой из стен. В зависимости от того, на какой стене он находится, мы изменяем координаты в соответствии с развёрткой комнаты и находим расстояние от паука до мухи с помощью функции [latex]distance[/latex].
В случае местонахождения паука в каком-либо из углов комнаты, но не на полу, мы должны рассмотреть два варианта его положения в развёртке и найти минимальное из них.
Ссылки
Условие задачи на сайте E-Olymp
Код решения задачи
Зачёл. Кстати, Вы знаете, что это вариант одной из головоломок Дьюдени. Если попадётся ссылка на первоисточник, можно добавить ссылку.