求Kattis Path Crossings问题的高效Python解法及时间排序逻辑

Core Approach #

The problem requires checking if two players' linear paths (moving between time-stamped points) intersect. Here's the streamlined solution:

1. Sort Points by Time: For each player, sort their movement points directly by the t value. Negative times are treated as smaller than positive ones (e.g., -10 < -2 < 0 < 7), which Python's default sorting handles seamlessly.
2. Generate Line Segments: Convert each player's sorted points into a list of time-bound line segments.
3. Check Overlapping Segments: Use a two-pointer technique to only compare segments whose time intervals overlap. For each overlapping pair, check if the line segments intersect (including edge cases like endpoint collisions).

Full Python Implementation #

def read_points():
    n = int(input())
    points = []
    for _ in range(n):
        t, x, y = map(int, input().split())
        points.append((t, x, y))
    # Sort points by time t (handles negative values naturally)
    points.sort()
    return points

def cross(o, a, b):
    # Calculate cross product of vectors OA and OB
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def on_segment(p, q, r):
    # Check if point p lies on segment qr (inclusive of endpoints)
    return (min(q[0], r[0]) <= p[0] <= max(q[0], r[0])) and \
           (min(q[1], r[1]) <= p[1] <= max(q[1], r[1]))

def segments_intersect(a1, a2, b1, b2):
    # Check if segments a1a2 and b1b2 intersect (covers all edge cases)
    # Early check for endpoint collisions
    if a1 == b1 or a1 == b2 or a2 == b1 or a2 == b2:
        return True
    
    c1 = cross(a1, a2, b1)
    c2 = cross(a1, a2, b2)
    c3 = cross(b1, b2, a1)
    c4 = cross(b1, b2, a2)
    
    # Check if segments straddle each other
    if (c1 * c2 < 0) and (c3 * c4 < 0):
        return True
    
    # Check if endpoints lie on the opposite segment
    if c1 == 0 and on_segment(b1, a1, a2):
        return True
    if c2 == 0 and on_segment(b2, a1, a2):
        return True
    if c3 == 0 and on_segment(a1, b1, b2):
        return True
    if c4 == 0 and on_segment(a2, b1, b2):
        return True
    
    return False

def main():
    def get_segments(points):
        # Convert sorted points into time-bound line segments
        segments = []
        for i in range(len(points)-1):
            t_start, x1, y1 = points[i]
            t_end, x2, y2 = points[i+1]
            segments.append((t_start, t_end, (x1, y1), (x2, y2)))
        return segments
    
    player1 = read_points()
    player2 = read_points()
    
    # Handle edge case: both players have only one point
    if len(player1) == 1 and len(player2) == 1:
        print("YES" if player1[0][1:] == player2[0][1:] else "NO")
        return
    
    segs1 = get_segments(player1)
    segs2 = get_segments(player2)
    
    i = j = 0
    len1, len2 = len(segs1), len(segs2)
    crossed = False
    
    # Two-pointer approach to check overlapping segments
    while i < len1 and j < len2:
        t1_start, t1_end, a1, a2 = segs1[i]
        t2_start, t2_end, b1, b2 = segs2[j]
        
        if t1_end < t2_start:
            i += 1
        elif t2_end < t1_start:
            j += 1
        else:
            if segments_intersect(a1, a2, b1, b2):
                crossed = True
                break
            # Move pointer for the segment that ends earlier
            i += 1 if t1_end <= t2_end else 0
            j += 1 if t2_end <= t1_end else 0
    
    # Handle edge case: single-point player lies on the other's path
    if not crossed:
        # Check if player1's single point is on any of player2's segments
        if len(player1) == 1:
            t_p, x_p, y_p = player1[0]
            pos_p = (x_p, y_p)
            for seg in segs2:
                t_s, t_e, b1, b2 = seg
                if t_s <= t_p <= t_e and segments_intersect(pos_p, pos_p, b1, b2):
                    crossed = True
                    break
        # Check if player2's single point is on any of player1's segments
        if len(player2) == 1:
            t_p, x_p, y_p = player2[0]
            pos_p = (x_p, y_p)
            for seg in segs1:
                t_s, t_e, a1, a2 = seg
                if t_s <= t_p <= t_e and segments_intersect(pos_p, pos_p, a1, a2):
                    crossed = True
                    break
    
    print("YES" if crossed else "NO")

if __name__ == "__main__":
    main()

Key Details #

• Time Comparison: No special logic is needed for negative t values—Python's default tuple sorting will order them correctly relative to positive times.
• Efficiency: The two-pointer approach runs in O(n + m) time (n and m are the number of points per player), avoiding the O(n*m) cost of checking all segment pairs.
• Edge Case Coverage: The code handles single-point players, endpoint collisions, and points lying directly on the other player's path.

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