Задача
В пустой прямоугольной комнате размерами $A \times B \times C$ (длина, ширина, высота) на пол упала уснувшая муха. Паук, находившийся на одной из стен, или на полу комнаты, начал двигаться к ней по кратчайшему пути.
На какое расстояние он при этом переместится?
Входные данные
В первой строке заданы размеры комнаты $A$, $B$, $C$. Во второй строке — координаты мухи $X_1$,$Y_1$ и паука $X_2$, $Y_2$, $Z_2$.
Все входные данные — целые числа, не превышающие $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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
import java.io.PrintStream; import java.util.Scanner; import java.lang.Math; public class Main { public static double distance (double X1,double X2,double Y1,double Y2) { return (Math.sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2))); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); double A = sc.nextDouble(); double B = sc.nextDouble(); double C = sc.nextDouble(); double X1 = sc.nextDouble(); double Y1 = sc.nextDouble(); double X2 = sc.nextDouble(); double Y2 = sc.nextDouble(); double Z2 = sc.nextDouble(); double result_distance = Double.MAX_VALUE; if (Z2==0) result_distance = distance(X1,X2,Y1,Y2);//"floor" case else { if (X2==0) { X2=-Z2; result_distance = distance (X1,X2,Y1,Y2); }//"left wall" case if (X2==A) { X2=A+Z2; result_distance = distance (X1,X2,Y1,Y2); }//"right wall" case if (Y2==0) { Y2=-Z2; result_distance = Math.min(result_distance, distance (X1,X2,Y1,Y2)); }//"near wall" case if (Y2==B) { Y2=B+Z2; result_distance = Math.min(result_distance, distance (X1,X2,Y1,Y2)); }//"distant wall" case } System.out.printf("%.2f", result_distance); } } |
Решение задачи
Суть решения задачи заключается в переходе от трехмерного пространства комнаты к двумерному с помощью «развёртки» комнаты на координатную плоскость.
Переведя координаты паука в комнате в его новые координаты в двумерном пространстве, все, что нам остается сделать — вычислить кратчайшее расстояние между двумя точками на плоскости с помощью функции $distance$.
В простейшем случае, если паук находится на полу комнаты, т.е. его координата $Z2$ нулевая, координаты паука $X2$ и $Y2$ в точности описывают его положение в координатной плоскости развёртки, и преобразовывать их не требуется.
В противном случае отдельно рассматриваем варианты расположения паука на каждой из стен. В зависимости от того, на какой стене он находится, мы изменяем координаты в соответствии с развёрткой комнаты и находим расстояние от паука до мухи с помощью функции $distance$.
В случае местонахождения паука в каком-либо из углов комнаты, но не на полу, мы должны рассмотреть два варианта его положения в развёртке и найти минимальное из них.