We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- All Contests
- ProjectEuler+
- Project Euler #144: Investigating multiple reflections of a laser beam.
- Discussions
Project Euler #144: Investigating multiple reflections of a laser beam.
Project Euler #144: Investigating multiple reflections of a laser beam.
Sort by
recency
|
6 Discussions
|
Please Login in order to post a comment
In order to solve this we must find the tangent of line that is reflected. Incident beam and reflected one form the same angle with the normal to the tangent line in point of reflection. Tangent line has the slope -(a/b) * (x / y) where x and y are point of intersection. Having the slope of reflected beam we can easily find its equation and point where it inercects with the ellipse. You sohuld avoid calculating the next intersection point by solving quadratic equation with delta and square roots. It's better to factorize this equation because we have only multiplying and division.
Anyone got some special test cases I might not be considering? I am getting wrong answer on some questions
All the test cases except Testcase0 are getting timed out. But i cannot check the testcases. Can any body give me some testcases.
Same here... It would be great to have few more TC.
WA on 4, 6-20. My algorithm is pretty general; not a lot of special cases. I think it might be getting hung up on numerical accuracy. Can anyone suggest some interesting test cases?
I used long double in c++, and it (surprisingly) passed without any precision issues. Didn't do anything special, except handle the case when the slope of the line is zero, and avoid taking square roots (you can factor out one of the solutions when you plug in the line into the ellipse equation, knowing that (x1,y1) satisfies both).
Ah, I was using C#.NET "double" which is only 64-bit precision. I think that's the best that the .NET libraries offer.
Just tried again with regular 64-bit double, and only #19 fails. You can use BigInteger to craft a "BigDecimal" class. Or you can convert everything to fractions and use a gcd() function to keep numerators/denominators small. Or you might be able to get away with "decimal" in C#, which has more precision than double.
64-bit floating-point precision is actually enough here. I passed using C++ double and also tested Python float (which is probably an underlying C double anyway). However my code only uses multiplications/divisions: Computing angles is not necessary for a reflection (this can be done through a projection) and, as said before, you can also avoid square roots here.
COMMENT