[Из песочницы] Разбор задачи «Зеркало в коридоре» и негодование17.02.2015 00:18

Хочу более подробно разобрать задачу из публикации «Олимпиады по программированию среди школьников», а также показать, что она действительно нетривиальная. Хотя в результате программа и состоит из трех присваиваний и двух сравнений, прийти к этому результату не так уж и просто, тем более, если нет под рукой справочника по аналитической геометрии.Итак, сразу договоримся, что всяческих округлений и погрешностей, связанных с представлением чисел с плавающей точкой, у нас не будет. Работать будем исключительно с целочисленными переменными, для этого прибегнем к очевидным хитростям. Хотя, на самом деле, здесь будет мало программирования и много математики. В этой работе использованы справочные материалы по ВУЗовской математике, а точнее один параграф из главы «Основы линейной алгебры и аналитической геометрии» [1].

Для начала напомню текст задачи:

Простуженный Петя лежал в постели, как вдруг кто-то открыл дверь. Пете было лень вставать и он посмотрел в зеркало, чтобы увидеть кто пришёл. Известны координаты вошедшего (его можно считать материальной точкой), необходимо узнать, удасться ли Пете увидеть отражение вошедшего в зеркале. Зеркало имеет форму круга с центром в начале координат и расположено в плоскости ax + by + cz = 0. Петю тоже можно считать материальной точкой. Гарантируется, что Петя и незнакомец не лежат в плоскости зеркала и что Петя всегда видит отражающую сторону зеркала. Если изображение попадает на границу зеркала, то Петя видит вошедшего. Так как и Петю и вошедшего можно считать материальными точками, Петя может увидеть отражение вошедшего как сквозь вошедшего, так и сквозь свое собственное отражение.

Что ж, «в лоб» к этой задаче не подступиться, разбор в указанном топике тоже не особо что-то «разжевывает». Поэтому я предлагаю упростить задачу и решить ее для двумерного пространства, а потом по аналогии перейти уже к трехмерному.Можно, конечно, рассмотреть даже и одномерный вариант, но смысла в нем мало, ибо зеркало превращается в точку и Петр увидит вошедшего только в том случае, когда они находятся по одну сторону от зеркала, т.е. если их координата имеет одинаковый знак.

Вычертим иллюстрацию к задаче:

Обозначим Петю точкой S, незнакомца точкой T, зеркало — отрезок прямой $Ax+By=0$ Исходные данные: R — радиус зеркала, коэффициенты A и B; $(x_{T};y_{T})$ — координаты вошедшего; $(x_{S};y_{S})$ — координаты Петра.

Алгоритм решения следующий: — Через точку T проводим прямую, перпендикулярную PQ; — На этой прямой отмечаем точку T` симметричную точке T относительно PQ — это будет изображение вошедшего, которое увидит (или не увидит) Петя; — Проведем прямую ST`; — Найдем точку пересечения PQ и ST`; — Проверим, принадлежит ли данная точка отрезку PQ

Итак, уравнение прямой, проходящей через точку T перпендикулярно $Ax+By=0$ выглядит следующим образом: $/frac{x-x_{T}}{A}=/frac{y-y_{T}}{B}$ или $Bx-Bx_{T}=Ay-Ay_{T}$ $Bx-Ay+(Ay_{T}-Bx_{T})=0$ Точка пересечения TT` и PQ является решением системы уравнений: $/left/{/begin{matrix} Ax+By=0// Bx-Ay+(Ay_{T}-Bx_{T})=0 /end{matrix}/right.}$ Домножим уравнения на A и B соответственно и сложим между собой: $/left/{/begin{matrix} A^{2}x+ABy=0// B^{2}x-ABy+B(Ay_{T}-Bx_{T})=0 /end{matrix}/right.}$ $(A^{2}+B^{2})x+B(Ay_{T}-Bx_{T})=0$ $x''_{T}=/frac{B^{2}x_{T}-ABy_{T}}{A^{2}+B^{2}}$ $y''_{T}=-/frac{A}{B}x''_{T}=/frac{A^{2}y_{T}-ABx_{T}}{A^{2}+B^{2}}$ Найденная точка $(x''_{T};y''_{T})$ — проекция точки T на прямую PQОпределим координаты точки T`: $x'_T=2x''_T-x_T=/frac{2B^2x_T-2ABy_T-(A^2+B^2)x_T}{A^2+B^2}=/frac{(B^2-A^2)x_T-2ABy_T}{A^2+B^2}$ $y'_T=2y''_T-y_T=/frac{2A^2y_T-2ABx_T-(A^2+B^2)y_T}{A^2+B^2}=/frac{(A^2-B^2)y_T-2ABx_T}{A^2+B^2}$

Два шага позади. Найдем уравнение прямой ST`: $/frac{x-x_S}{x'_T-x_S}=/frac{y-y_S}{y'_T-y_S}$ или $(y'_T-y_S)(x-x_S)=(x'_T-x_S)(y-y_S)$ Подставим выражения для координат T`: $(/frac{(A^2-B^2)y_T-2ABx_T}{A^2+B^2}-y_S)(x-x_S)=//=(/frac{(B^2-A^2)x_T-2ABy_T}{A^2+B^2}-x_S)(y-y_S)$ Уходим к целочисленному исчислению — умножаем уравнение на $(A^2+B^2)$ : $((A^2-B^2)y_T-2ABx_T-(A^2+B^2)y_S)(x-x_S)=//=((B^2-A^2)x_T-2ABy_T-(A^2+B^2)x_S)(y-y_S)$ Самое время ввести замену: $M=(A^2-B^2)y_T-2ABx_T-(A^2+B^2)y_S//N=(B^2-A^2)x_T-2ABy_T-(A^2+B^2)x_S$ тогда уравнение ST` принимает вид: $M/cdot (x-x_S)=N/cdot (y-y_S)/Rightarrow Mx-Ny+(Ny_S-Mx_S)=0$

Точка пересечения PQ и ST` является решением системы: $/left/{/begin{matrix}Mx-Ny+(Ny_S-Mx_S)=0//Ax+By=0/end{matrix}/right.}$ $y=-/frac{A}{B}x$ $Mx+/frac{AN}{B}x+(Ny_S-Mx_S)=0//(BM+AN)x=BMx_S-BNy_S$ $x=/frac{BMx_S-BNy_S}{BM+AN}$ $y=-/frac{A}{B}/cdot/frac{BMx_S-BNy_S}{BM+AN}=/frac{ANy_S-AMx_S}{BM+AN}$

Ну и, наконец, расстояние от центра координат до найденной точки: $R'=/sqrt{x^2+y^2}$ Уходим от радикалов: $(R')^2=x^2+y^2=/frac{(BMx_S-BNy_S)^2+(ANy_S-AMx_S)^2}{(BM+AN)^2}$ Теперь, если найденное R' будет не более заданного R, то наш несчастный Петр увидит все-таки вошедшего незнакомца.В сравнении $/frac{(BMx_S-BNy_S)^2+(ANy_S-AMx_S)^2}{(BM+AN)^2}/leq R^2$ обе части неравенства умножим на заведомо положительное (т.к. четная степень) $(BM+AN)^2$ т.е. нас интересует истинность выражения $(BMx_S-BNy_S)^2+(ANy_S-AMx_S)^2/leq R^2(BM+AN)^2$

К чему я все это так подробно расписываю? Просто для того, чтобы показать какой объем работ должен проделать участник олимпиады для решения этой задачи, а ведь все эти формулы перпендикулярных прямых не входят в школьный курс математики, участник должен сам до них дойти логическим путем? При этом ему на эту задачу отведено в среднем 30 минут. Так ведь задача-то еще и не решена на самом-то деле. Во-первых надо все тоже самое проделать для трехмерного пространства, что еще более трудоемко, а во-вторых здесь не рассмотрено находятся ли мальчик и его гость по одну сторону от зеркала…

Чтож, нам-то цейтнот не грозит, поэтому продолжим.Разберемся с «зазеркальем».У меня такое решение (хотя оно тоже не сразу пришло в голову, сначала я думал о переходе к системе координат связанной с прямой зеркала, но там «некрасивые» тригонометрические функции) — через точки S и T проведем прямые параллельные заданной $Ax+By=0$ . Параллельные прямые имеют кратные коэффициенты при x и y, т.е. $/frac{A_1}{A_2}=/frac{B_1}{B_2}$ , разница только в свободном члене. Мы ничего выдумывать не будем и возьмем эти коэффициенты равными заданным A и B.Тогда уравнение прямой, проходящей через точку S параллельно PQ имеет вид: $/frac{x-x_S}{-B}=/frac{y-y_S}{A}$ или $A(x-x_S)+B(y-y_S)=0/Rightarrow Ax+Bx-(Ax_S+By_S)=0$ Вот, в зависимости от знака свободного члена $-(Ax_S+By_S)$ прямая будет находиться с одной либо с другой стороны от заданной.Аналогично для прямой, проходящей через T: $Ax+Bx-(Ax_T+By_T)=0$

Сделаем следующее: найдем значение произведения $(Ax_S+By_S)(Ax_T+By_T)$ и сравним его с нулем: если больше нуля — точки расположены по одну сторону от прямой, если меньше — по разные и Петя уже точно гостя своего не увидит, ну и промежуточный ноль — тоже удовлетворяет, т.к. в этом случае как минимум одна из точек лежит на заданной прямой.

Ну и напоследок приведу текст программы для трехмерного мира, т.е. для исходного условия задачи:

src package ru.andrewn;

import static java.lang.System.out;

public class Program {

public static void main (String[] args) { java.util.Scanner sc = new java.util.Scanner (System.in); out.println («Введите r:»); int R = sc.nextInt (); out.println («Введите a, b и c:»); int A = sc.nextInt (); int B = sc.nextInt (); int C = sc.nextInt (); out.println («Введите положение Петра (xп, yп и zп):»); int xx = sc.nextInt (); int yy = sc.nextInt (); int zz = sc.nextInt (); out.println («Введите положение входящего (x0, y0 и z0):»); int x0 = sc.nextInt (); int y0 = sc.nextInt (); int z0 = sc.nextInt (); if ((A*x0+B*y0+C*z0)*(A*xx+B*yy+C*zz) >= 0) { int M = (B*B+C*C-A*A)*x0–2*A*B*y0–2*A*C*z0-(A*A+B*B+C*C)*xx; int N = (A*A+C*C-B*B)*y0–2*A*B*x0–2*B*C*z0-(A*A+B*B+C*C)*yy; int K = (A*A+B*B-C*C)*z0–2*A*C*x0–2*B*C*y0-(A*A+B*B+C*C)*zz; if ((A*M+B*N+C*K)*(A*M+B*N+C*K)*R*R >= ((B*N+C*K)*xx-B*M*yy-C*M*zz)*((B*N+C*K)*xx-B*M*yy-C*M*zz) + ((A*M+C*K)*yy-A*N*xx-C*N*zz)*((A*M+C*K)*yy-A*N*xx-C*N*zz) + ((A*M+B*N)*zz-A*K*xx-B*K*yy)*((A*M+B*N)*zz-A*K*xx-B*K*yy)) out.println («Петр увидит входящего»); else out.println («Петр не увидит входящего»); } else out.println («Петр не увидит входящего»); sc.close (); } } Простите за кривизну кода, я далеко не программист.Если будут желающие — могу приложить и математические выкладки для трехмерного мира.

Резюме Мораль сей публикации в том, что составителям задач для олимпиад следует все же более тщательно проверять, на сколько трудоемко решение задачи и каких познаний оно требует для успешного выполнения в отведенное время.Литература 1. Корниенко, В.С. Справочный материал по математике: Пособие для самообразования [Электронный ресурс] / В.С. Корниенко; Волгогр. гос. с.-х. акад. Волгоград, 2010. 284 с.