659 - Reflections

[Pasq]

Is input and output corect ? In my opinion output for
3
3 3 2
7 7 1
8 1 1
3 8 1 -4
should be
1 inf
The ray goes from point (3,8), is directed to point (1,-4), hits the 1'st sphere and goes to infinitiy. Am I right ?

[jpfarias]

I don't know if this is true, but my first attemp on solving this problem give me this answer also. May be someone who got AC can tell us if this is really true or not, or even show us a graphic with the rays / circles...


JP!

[jpfarias]

How do you calculate the reflected ray?

I'm using this formula: R = V - 2 * ( V . N ) * N
Where:
R => The resulting ray
V => The actual ray
N => The normal in the point it hits the circle

I've found this formula in a book of algebra. Is this wrong?

I'm also reducing the ray to 0.5 * (the normalized ray) to avoid start pointing too far.

JP!

[Per]

Pasq: My accepted program outputs

Code: Select all

1 2 1 3 inf

for your input.

(After hitting 1, the ray goes from (3.79,4.84) and hits 2 in (6.32, 6.26).)

[jpfarias]

Hi!

Is my formula above correct? If not, can you tell me the correct one?

Thanks,

JP!

[Per]

It could be, but I'm too tired at the moment to check.
If it was in a book it's probably right.

I didn't use vector algebra at all to calculate the reflected ray. My approach was to simply draw the circle and the rays on a piece of paper and derive a formula for the outgoing angle in terms of the incoming angle and the angle of the tangent of the circle.

Note that (1, -4) in the first test case is the direction the ray is heading in, not a point towards which it is heading.

[jpfarias]

Ok, so, can you tell me what is your formula to calculate the resulting angle?

And about the point (1,-4) in the first test case, I know it is the direction, so I add it to original point to get the vector, the resulting is a vector starting at (3,8) with endpoint in (4,4), with these 2 points I calculate the line equation to then calculate the intersection with the circles, by finding the roots of the equations of line and circle.

I don't know it is clear enough, but I hope you understand what I mean...

JP!

[Per]

If I read my code correctly, I used out=2*v-in (the equation in+out=2*v makes sense, so I think it's right), where out is the outgoing angle, in is the incoming angle, and v is the angle of the tangent of the circle.

I find the intersection the same way as you do (be careful to choose the right intersection point!).

[Raziel]

Pasq: My accepted program outputs

Code: Select all

1 2 1 3 inf

for your input.

(After hitting 1, the ray goes from (3.79,4.84) and hits 2 in (6.32, 6.26).)

I have question about precision those numbers ... should i round it like you ?

[minskcity]

Could anybody verify my intersection points for the first testcase?

Code: Select all

(3.0000000000,8.0000000000)
(3.7907389103,4.8370443587)
(6.3236397189,6.2634290461)
(4.9762157582,3.3075244334)
(7.0026212522,1.0723576776)

Thanks in advance

[daveon]

Hi,

Even though you got it AC, the points are correct.

[Darko]

Alright... how about direction vectors?

Code: Select all

(1.0,-4.0)
(2.8408172256739066,1.599785580545551)
(-1.2057307402031512,-2.6450658148092554)
(2.181912958403373,-2.406694673395701)
(-2.327801534169951,-1.9192784243630285)

I don't think there is much to this - find the closest intersection of the ray and circles, find reflection of the origin of the ray, set new ray from intersection to the reflection, keep going until you either hit nothing (print "inf" and break) or you've done it 10 times. If after 10th time there is no intersection, print "inf", otherwise print "...".

I triple checked both my ray-circle intersection and the reflection. I have no idea what might be wrong, unless input contains cases they said it wouldn't.

[Darko]

I was just being stupid (I assumed something worked without testing). If someone else has troubles with this one, try these two cases:

Code: Select all

10
0 0 1
1 3 1
2 0 1
3 3 1
4 0 1
5 3 1
6 0 1
7 3 1
8 0 1
9 3 1
-1 2 1 -1
11
0 0 1
1 3 1
2 0 1
3 3 1
4 0 1
5 3 1
6 0 1
7 3 1
8 0 1
9 3 1
10 0 1
-1 2 1 -1
0