ISI CSB 2017 C6

Question

Let P = {P1(x1, y1), P2(x2, y2), . . . , Pn(xn, yn)} be a set of n points located within a rectangle such that none of the points touches its boundary. The top-left corner of the rectangle is at the origin O(0, 0). A plane mirror is placed along the lower edge of the rectangle (as shown in the figure). A point source of light is placed at O. The source can emit a single ray of light at any angle θ. Write an algorithm (pseudo-code) to compute a value of θ for which the corresponding ray and its reflection together pass through the maximum number of points of the set P. For example, in the figure below, the ray R1 at angle θ1 (denoted by a solid line), passes through 3 points, while the ray R2 at angle θ2 (denoted by a dashed line), passes through only 2 points. You will get full credit only if your algorithm takes O(n log n) time.

Answer 1

Look at the image above here the point P₄' is the image of the point P₄

If the light ray reaches the point P₄ after getting bounced from the mirror then the light ray would have reached the point P₄' when there will be no mirror.

So, just generate n images of the given n points and remove the mirror. 

Then our problem would be reduced to find the value of θ such that the light ray would cover the maximum number of points in its path.

This could be solved with the help of the algorithm written below.

1) Take an array A[2n] 

2) Calculate the angle made by each point with the x-axis which will be tan^-1 (y/x) and store the value of the angle made by the point P_i  in A[i]. This would take O(n) time.

3) Sort the array A. This would take O n(log n) time.

4) Find which angle in the array A is repeated maximum no. of times and return that angle this would take O(n) time.

Thus our whole algorithm would take O n(log n) time.