February 16, 2015 at 22:44Analysis of the task “Mirror in the corridor” and indignation
I want to analyze the task in more detail from the publication of the “Programming Olympiad among schoolchildren” , and also show that it is really non-trivial. Although the program as a result consists of three assignments and two comparisons, to come to this result is not so simple, especially if there is no handbook on analytical geometry at hand.
So, we’ll immediately agree that we won’t have any roundings and errors associated with the representation of floating-point numbers. We will work exclusively with integer variables, for this we will resort to obvious tricks. Although, in fact, there will be little programming and a lot of math. In this work, reference materials on high school mathematics were used, or rather one paragraph from the chapter "Fundamentals of linear algebra and analytic geometry" [1].
To start, I recall the text of the task:
Well, we cannot approach this task “on the forehead”; parsing in the specified topic is also not really “chewing” something. Therefore, I propose to simplify the problem and solve it for two-dimensional space, and then, by analogy, move on to three-dimensional.
You can, of course, consider even a one-dimensional version, but there is little sense in it, because the mirror turns into a point and Peter sees the person who enters only if they are on one side of the mirror, i.e. if their coordinate has the same sign.
We draw an illustration of the problem:
Denote Petya by the point S , the stranger by the point T , the mirror is a straight line segment
Initial data: R is the radius of the mirror, coefficients A and B ;
- coordinates of the entered;
- coordinates of Peter.
The solution algorithm is as follows:
- Through point T, draw a line perpendicular to PQ ;
- On this line we mark the point T` symmetric to the point T relative to PQ - this will be the image of the person who entered, who will see (or not see) Petya;
- Draw a direct ST` ;
- Find the intersection point of PQ and ST` ;
- Check whether the given point belongs to the segment PQ
So, the equation of the line passing through the point T is perpendicular to thefollowing:
or 
The intersection point of TT` and PQ is the solution of the system of equations:
We multiply the equations by A and B, respectively, and add each other:
The found point
is the projection of the point T onto the straight line PQ
Determine the coordinates of the point T` :
Two steps behind. Find the equation of the straight line ST` :
or 
Substitute the expressions for the coordinates T` :
Go to the integer calculus - multiply the equation by
: It's
time to introduce a replacement:
then the equation ST` takes the form:
The intersection point of PQ and ST` is the solution to the system:
Well, finally, the distance from the center of coordinates to the found point:
We move away from the radicals:
Now, if the found R ' is no more than the given R , then our unfortunate Peter will still see the stranger who has come in.
In comparison
, we multiply both sides of the inequality by a known positive (since an even degree) 
i.e. we are interested in the truth of expression
Why am I writing all this in such detail? Just in order to show how much work a participant in the olympiad should do to solve this problem, and yet all these formulas of perpendicular lines are not included in the school course of mathematics, does the participant himself have to get to them in a logical way? Moreover, he was assigned an average of 30 minutes to this task. So after all, the task has not yet been solved in fact. Firstly, you need to do the same for three-dimensional space, which is even more time-consuming, and secondly, it is not considered here whether the boy and his guest are on the same side of the mirror ...
Well, we are not in danger of time pressure, so we will continue.
We will deal with the "looking glass".
I have such a solution (although it also didn’t immediately come to my head, at first I thought about moving to a coordinate system associated with a straight mirror, but there are ugly trigonometric functions) - through points S and T we draw straight lines parallel to the given one. Parallel lines have multiple coefficients at x and y , i.e. 
, the difference is only in the free member. We did not invent anything, and will take these coefficients are given A and Bed and .
Then the equation of the line passing through the point S parallel to PQ has the form:
or 
Here, depending on the sign of the free term
the line will be located on one or the other side of the given one.
Similarly, for the line passing through T :
We do the following: find the value of the product
and compare it with zero: if it is more than zero, the points are located on one side of the line, if it is less than that, they are different and Petya will not see his guest for sure, well, and the intermediate zero - also satisfies, because in this case, at least one of the points lies on a given line.
Well, finally, I will give the text of the program for the three-dimensional world, i.e. for the initial condition of the problem:
Sorry for the curvature of the code, I'm far from a programmer.
If there are those who wish, I can also attach mathematical calculations for the three-dimensional world.
The moral of this publication is that the compilers of the tasks for the olympiads should nevertheless more thoroughly check how laborious the solution of the problem is and what knowledge it requires for successful completion in the allotted time.
1. Kornienko, V.S. Reference material in mathematics: A manual for self-education [Electronic resource] / V.S. Kornienko; Volgogr. state S.-kh. Acad. Volgograd, 2010.284 s.
So, we’ll immediately agree that we won’t have any roundings and errors associated with the representation of floating-point numbers. We will work exclusively with integer variables, for this we will resort to obvious tricks. Although, in fact, there will be little programming and a lot of math. In this work, reference materials on high school mathematics were used, or rather one paragraph from the chapter "Fundamentals of linear algebra and analytic geometry" [1].
To start, I recall the text of the task:
Cold Petya was lying in bed, when suddenly someone opened the door. Petya was too lazy to get up and he looked in the mirror to see who had come. The coordinates of the person entering are known (it can be considered a material point), it is necessary to find out if Pete will be able to see the reflection of the person entering in the mirror. The mirror has the shape of a circle centered at the origin and is located in the plane ax + by + cz = 0. Petya can also be considered a material point. It is guaranteed that Petya and the stranger do not lie in the plane of the mirror and that Petya always sees the reflecting side of the mirror. If the image hits the border of the mirror, then Petya sees the person entering. Since both Petya and the person entering can be considered material points, Petya can see the reflection of the person entering both through the person entering and through his own reflection.
Well, we cannot approach this task “on the forehead”; parsing in the specified topic is also not really “chewing” something. Therefore, I propose to simplify the problem and solve it for two-dimensional space, and then, by analogy, move on to three-dimensional.
You can, of course, consider even a one-dimensional version, but there is little sense in it, because the mirror turns into a point and Peter sees the person who enters only if they are on one side of the mirror, i.e. if their coordinate has the same sign.
We draw an illustration of the problem:
Denote Petya by the point S , the stranger by the point T , the mirror is a straight line segment
Initial data: R is the radius of the mirror, coefficients A and B ;
- coordinates of the entered; - coordinates of Peter. The solution algorithm is as follows:
- Through point T, draw a line perpendicular to PQ ;
- On this line we mark the point T` symmetric to the point T relative to PQ - this will be the image of the person who entered, who will see (or not see) Petya;
- Draw a direct ST` ;
- Find the intersection point of PQ and ST` ;
- Check whether the given point belongs to the segment PQ
So, the equation of the line passing through the point T is perpendicular to the
following:or The intersection point of TT` and PQ is the solution of the system of equations:
We multiply the equations by A and B, respectively, and add each other:
The found point
is the projection of the point T onto the straight line PQDetermine the coordinates of the point T` :
Two steps behind. Find the equation of the straight line ST` :
or Substitute the expressions for the coordinates T` :
Go to the integer calculus - multiply the equation by
: It's time to introduce a replacement:
then the equation ST` takes the form:
The intersection point of PQ and ST` is the solution to the system:
Well, finally, the distance from the center of coordinates to the found point:
We move away from the radicals:
Now, if the found R ' is no more than the given R , then our unfortunate Peter will still see the stranger who has come in.
In comparison
, we multiply both sides of the inequality by a known positive (since an even degree) i.e. we are interested in the truth of expression
Why am I writing all this in such detail? Just in order to show how much work a participant in the olympiad should do to solve this problem, and yet all these formulas of perpendicular lines are not included in the school course of mathematics, does the participant himself have to get to them in a logical way? Moreover, he was assigned an average of 30 minutes to this task. So after all, the task has not yet been solved in fact. Firstly, you need to do the same for three-dimensional space, which is even more time-consuming, and secondly, it is not considered here whether the boy and his guest are on the same side of the mirror ...
Well, we are not in danger of time pressure, so we will continue.
We will deal with the "looking glass".
I have such a solution (although it also didn’t immediately come to my head, at first I thought about moving to a coordinate system associated with a straight mirror, but there are ugly trigonometric functions) - through points S and T we draw straight lines parallel to the given one
. Parallel lines have multiple coefficients at x and y , i.e. , the difference is only in the free member. We did not invent anything, and will take these coefficients are given A and Bed and . Then the equation of the line passing through the point S parallel to PQ has the form:
or Here, depending on the sign of the free term
the line will be located on one or the other side of the given one. Similarly, for the line passing through T :
We do the following: find the value of the product
and compare it with zero: if it is more than zero, the points are located on one side of the line, if it is less than that, they are different and Petya will not see his guest for sure, well, and the intermediate zero - also satisfies, because in this case, at least one of the points lies on a given line. Well, finally, I will give the text of the program for the three-dimensional world, i.e. for the initial condition of the problem:
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();
}
}Sorry for the curvature of the code, I'm far from a programmer.
If there are those who wish, I can also attach mathematical calculations for the three-dimensional world.
Summary
The moral of this publication is that the compilers of the tasks for the olympiads should nevertheless more thoroughly check how laborious the solution of the problem is and what knowledge it requires for successful completion in the allotted time.
Literature
1. Kornienko, V.S. Reference material in mathematics: A manual for self-education [Electronic resource] / V.S. Kornienko; Volgogr. state S.-kh. Acad. Volgograd, 2010.284 s.