求使入射光线与反射光线共过最多点的θ值的O(n log n)算法

Hey there! Great question—this is a classic problem where the mirror trick (also called the method of images) turns the reflection problem into a straightforward line-counting task, which lets us hit that O(n log n) time requirement. Let me break this down step by step, with pseudocode included.

Core Insight: Mirror the Points #

Instead of thinking about light bouncing off the bottom mirror, we can "mirror" each point across the mirror edge and treat the reflected light path as a straight line from the origin O to the mirrored point. This works because the law of reflection (angle in = angle out) makes the bounced path mathematically equivalent to a straight line to the mirrored point.

For every original point ( P(x,y) ):

• If ( P ) lies on the incident ray (light from O before hitting the mirror), it's just a regular point on a line from O.
• If ( P ) lies on the reflected ray (after the bounce), it corresponds to its mirrored twin ( P'(x, 2H - y) ) (where ( H ) is the y-coordinate of the bottom mirror edge) lying on a straight line from O.

To avoid floating-point precision issues, we represent each direction as a reduced fraction (simplest integer ratio of x to y). We also standardize the sign (always make the y-component positive) so identical directions get the same marker.

Pseudocode (O(n log n) Time) #

// Input: List of points P, rectangle height H (mirror at y=H)
function findOptimalAngle(P, H):
    directionEntries = []
    
    for each (x, y) in P:
        // 1. Add direction for incident ray (O → P)
        gcdIncident = gcd(abs(x), abs(y))
        normIncidentX = x / gcdIncident
        normIncidentY = y / gcdIncident
        // Ensure positive y to standardize direction
        if normIncidentY < 0:
            normIncidentX = -normIncidentX
            normIncidentY = -normIncidentY
        directionEntries.append( ( (normIncidentX, normIncidentY), "incident" ) )
        
        // 2. Add direction for reflected ray (O → mirrored P)
        mirroredY = 2 * H - y
        gcdReflected = gcd(abs(x), abs(mirroredY))
        normReflectedX = x / gcdReflected
        normReflectedY = mirroredY / gcdReflected
        // Ensure positive y to standardize direction
        if normReflectedY < 0:
            normReflectedX = -normReflectedX
            normReflectedY = -normReflectedY
        directionEntries.append( ( (normReflectedX, normReflectedY), "reflected" ) )
    
    // Sort entries by their direction marker (first x, then y)
    sort directionEntries by (entry[0][0], entry[0][1])
    
    maxPoints = 0
    currentDir = null
    countIncident = 0
    countReflected = 0
    
    // Traverse sorted entries to count total points per direction
    for each (dir, type) in directionEntries:
        if dir != currentDir:
            // Calculate total points for the previous direction
            total = countIncident + countReflected
            if total > maxPoints:
                maxPoints = total
            // Reset for new direction
            currentDir = dir
            countIncident = 0
            countReflected = 0
        
        // Update counts based on entry type
        if type == "incident":
            countIncident += 1
        else:
            countReflected += 1
    
    // Don't forget the last direction in the list
    finalTotal = countIncident + countReflected
    if finalTotal > maxPoints:
        maxPoints = finalTotal
    
    return maxPoints

Key Details & Complexity #

• Direction Standardization: Reducing directions to simplest integer ratios avoids precision errors from floating-point angles. The sign rule ensures identical ray directions (even if represented with opposite signs) are grouped together.
• Time Complexity: The sorting step dominates the time, taking ( O(n \log n) ) (we have 2n entries to sort). All other steps are ( O(n) ), so the total time is ( O(n \log n) ), which meets your requirement.
• Count Interpretation: For each direction, countIncident is the number of points on the incident ray, and countReflected is the number of points on the corresponding reflected ray. Adding them gives the total points covered by that angle's incident + reflected rays.

内容的提问来源于stack exchange，提问作者Kushagra Chatterjee