The Gateway to Computer Science Excellence

0 votes

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.

+1 vote

Look at the image above here the point P_{4}' is the image of the point P_{4}

If the light ray reaches the point P_{4} after getting bounced from the mirror then the light ray would have reached the point P_{4}' 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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,388 answers

198,576 comments

105,414 users