Project Euler is a website offering math challenges solvable by programming - usually few tens lines of code are enough. Last friday, after more than a year of Euler abstinence, I decided to have a look at it again, and ran across this cool problem (#144, check it out
here).
So the goal is to find the number of times the laser beam will hit the ellipse-shaped cell before exiting through the input cavity.
First, let's formulate the problem with simple trigonometry. Have a look at the schema below:
The laser beam comes from A and hits the ellipse at point 0. We can calculate the slope m0: (yO-yA)/(xO-xA); we can also calculate the slope m1: -4*x/y. We need to calculate slope m2 and deduce B in order to iterate this process (find the next point of impact).
It appears clear that:
a = a0-a1
and
a = a1+PI-a2
Therefore:
tan(a) = tan(a0-a1)
= (tan(a0)-tan(a1))/(1+tan(a0)*tan(a1))
= (m0-m1)/(1+m0*m1)
and
tan(a) = tan(a1+PI-a2)
= tan(a1-a2)
= (tan(a1)-tan(a2))/(1+tan(a1)*tan(a2))
= (m1-m2)/(1+m1*m2)
Let's set X = (m0-m1)/(1+m0*m1)
X = (m1-m2)/(1+m1*m2)
-> m2 = (m1-X)/(1+X*m1)
We have the slope m2 of the reflected beam (OB). With the coordinates of O (x0,y0), we have the equation of the line:
y = a*x+b, with a=m2 and b=y0-m2*x0
The last step is calculate the coordinates of B. We have:
- the equation of the ellipse: 4*x^2+y^2 = 100
- the equation of (0B): y = m2*x+b
It boils down to solving the quadratic:
x^2*(4+a^2) + x*(2*a*b) + (b^2-100) = 0
And then we yield the coordinates of B. After a few
300-and-something iterations (nah I wouldn't spoil your Euler fun) you'll find out the reflected point falls onto the exit hole. Problem solved!
4 comments:
This line:
-> m2 = (m1-X)(1+X*m1)
Should read:
-> m2 = (m1-X)/(1+X*m1)
Fixed. Thank you!
Hey I need some help with this one. If you are willing to take a look at my code, please email me at koroluka@gmail.com
Nevermind, I got it. http://andrewkoroluk.com/wordpress/?p=48
Post a Comment