myprogrammingblog

[myprogrammingblog]

mirrors // usaco 2013 jan B1

p: By installing reflective fences at different locations on the farm, FJ hopes to be able to see a position (a, b) from (0, 0). Fence i appears at (x_i, y_i) and is tilted 45 degrees (either like ‘\’ or ‘/’). FJ sits at (0, 0) and looks directly to the right (in the +x direction). His gaze bounces 90 degrees off the mirrors he sees. Unfortunately, one of the mirrors might be oriented incorrectly (’\’ is supposed to be ‘/’ or v.v.).

in:

(L1) ints N (number of fences) (1<= N <=200) , a, b (location we want to see).

(L2...1+N) fence i described in “x_i y_i \” or “x_i y_i /” (all coordinates, including a and b, lie in between -1,000,000 and 1,000,000).

out:

The index of the first fence for which toggling that fence allows FJ to see the point (a, b). If FJ can already see the point (a, b), output 0, or if there is no way he can see (a, b) even after toggling up to one fence, output -1.

s: In ‘mirrors’, we can store all the mirrors in a 2D array. For example, say we have mirrors at (3, 8), (3, 4), and (4, 4).

x[4]={3, 4}, x[8]={3}, y[3]={4, 8}, and y[4]={4}.

This way we don’t have to store the points in a 2D array, which would take too much memory. Note that this is kind of like coordinate compression, just without the actual graphing.

At each point, we can simulate the problem by following the light beam. Each reflection can be found by scanning the array for the next mirror, then changing the location and direction of the light in accordance. Set the italicized to be a function check( ). Simulate it initially, then check( ) what happens when each mirror is flipped, in order of index. If a solution is found such that the light will reach (a,b), print the index of the mirror. Otherwise, remember to output -1.