Алгоритм нахождения максимального количества баллов

Question

Пусть P = {P1 (x1, y1), P2 (x2, y2),.,,, Pn (xn, yn)} - набор из n точек, расположенных внутри прямоугольника, так что ни одна из точек не касается его границы.Верхний левый угол прямоугольника находится в начале координат O (0, 0).Плоское зеркало размещается вдоль нижнего края прямоугольника (как показано на рисунке).Точечный источник света расположен в O. Источник может излучать один луч света под любым углом θ.

Написать алгоритм (псевдо-код) для вычисления значения θ, для которого соответствующий луч и его отражение вместе проходят через максимальное число точек из набора P.

Например, на рисунке луч R1 под углом θ1 (обозначен сплошной линией), проходит через 3 точки, а луч R2 под углом θ2 (обозначен пунктирной линией) проходит только через 2 точки.Вы получите полный кредит, только если ваш алгоритм занимает O (n log n) времени.

................................................

Я бы сделал эту проблему, если бы нашел значение θ таким, чтобы максимальное количество точекна плоскости лежит падающий луч.

В то время я рассчитал бы значение θ для каждой точки, сфокусировав луч света на каждой точке и сохранив значения θ для точек в массиве.

Тогда наша задача сводится к тому, чтобы найти максимальное количество повторяющихся элементов в массиве.Это можно решить за O (n) раз.

Но я не знаю, как обращаться с отраженным лучом.Я искал в интернете, но тщетно.Пожалуйста помоги.

Answer 1

Один из подходов заключается в использовании метода изображений , который заменяет эффект отражений введением «зеркальных точек» на противоположной стороне отражающей поверхности.

Предположим, чтозеркало определяется плоскостью y=-b, тогда каждая точка (x_i, y_i) будет использоваться для создания отраженной версии самого себя.Эта дополнительная точка будет иметь такую ​​же x-координату, но y-координату на симметрично противоположном расстоянии от зеркала, то есть -b - (y_i + b), что равно -2b - y_i.(В вашем случае все y_i являются отрицательными.) Эта отраженная версия каждой точки точно моделирует геометрию луча, который достигает исходной точки после отскока от зеркала.После этого мы можем игнорировать зеркало и просто работать с 2N точками.

Итак, псевдокод для вашего алгоритма может выполнить что-то вроде этого:

• Создать дополнительный набор из Nточки под зеркальной поверхностью с использованием метода изображений
• Рассчитайте угол каждой из 2N точек от начала координат, используя atan2(y_i, x_i).Это занимает время порядка N.
• Группирует точки по их углам от начала координат, что эквивалентно их сортировке и обнаружению изменений между соседними значениями в списке, что занимает время порядка N (log N).
• Подсчитайте количество очков в каждой группе.(Это занимает время меньше, чем N.)
• Найдите группу с наибольшим количеством участников.

Answer 2

Положение зеркала не определено, поэтому предположим y = -1 для конкретности. Чтобы отразить свет в точку (x, y) с y > -1, нам нужно нацелиться от (0, 0) на (x/(y+1), -1). Эта точка может быть получена из наблюдения, что прямоугольный треугольник, созданный источником и точкой отражения, аналогичен прямоугольному треугольнику, сделанному целью и точкой отражения.