判断2D平面不相交圆集能否用直线平分为两等份的算法问询

Hey there! I’ve wrestled with geometric partitioning problems like this before, so let’s break this down into a concrete, code-ready algorithm that’ll solve your problem.

You need to determine if there’s a straight line that splits an even set of non-touching 2D circles into two equal-sized subsets, with the line never passing through any circle.

First, a key simplification: since circles don’t touch or overlap, a circle lies entirely on one side of a line if and only if its center lies on that side (as long as the line is far enough from the center to not intersect the circle). This lets us reduce the problem to working with circle centers, while keeping track of radii to validate line placement.

1. Handle Edge Cases First #

• If there are only 2 circles: Since they don’t touch, you can always draw a line between them that splits them perfectly. Return True immediately.
• If the input has an odd number of circles: Return False (your problem specifies even counts, but this is a safe guard).

2. Enumerate Critical Directions #

For any valid split line, rotating it will only change the count of circles on each side when the line is perpendicular to the line connecting two circle centers. We only need to check these critical directions (plus basic axis directions to cover edge cases):

• For every pair of circle centers, calculate the direction perpendicular to their connecting line.
• Normalize these directions to avoid duplicates (e.g., ensure the first non-zero component is positive).

3. Check Each Direction for Valid Splits #

For each critical direction:

1. Project Centers: Project each circle’s center onto a line perpendicular to the critical direction. This gives us a 1D value for each center.
2. Sort Projections: Sort these 1D projection values along with their corresponding circle radii.
3. Validate Split Space: Look for a gap between the k-th and (k+1)-th projection (where k = total circles / 2) that’s wide enough to fit a line without intersecting either adjacent circle. Specifically:
   • Calculate the minimum distance the line needs to be from the rightmost center in the left subset.
   • Calculate the minimum distance the line needs to be from the leftmost center in the right subset.
   • If these two distances don’t overlap, a valid split line exists in this gap.

import math

def can_split_circles(circles):
    n = len(circles)
    if n % 2 != 0:
        return False
    target_count = n // 2

    # Edge case: 2 non-touching circles always have a valid split
    if n == 2:
        return True

    # Collect all critical directions (perpendicular to pairs of centers)
    directions = set()
    # Add axis directions to cover edge cases
    directions.add((1, 0))
    directions.add((0, 1))

    for i in range(n):
        x1, y1, r1 = circles[i]
        for j in range(i + 1, n):
            x2, y2, r2 = circles[j]
            dx = x2 - x1
            dy = y2 - y1
            # Skip duplicate centers (impossible per problem constraints)
            if dx == 0 and dy == 0:
                continue
            # Get perpendicular direction vector
            perp_dir = (-dy, dx)
            # Normalize direction to avoid duplicates
            if perp_dir[0] == 0:
                if perp_dir[1] < 0:
                    perp_dir = (-perp_dir[0], -perp_dir[1])
            else:
                if perp_dir[0] < 0:
                    perp_dir = (-perp_dir[0], -perp_dir[1])
            directions.add(perp_dir)

    # Check each direction for valid splits
    for a, b in directions:
        # Calculate projection of each center onto the perpendicular line
        projections = []
        for x, y, r in circles:
            proj_val = b * x - a * y
            projections.append((proj_val, r))
        # Sort projections by their 1D value
        projections.sort()
        dir_norm = math.hypot(a, b)
        if dir_norm == 0:
            continue

        # Check if we can split after target_count elements
        left_proj, left_r = projections[target_count - 1]
        right_proj, right_r = projections[target_count]
        # Calculate safe bounds for the split line
        left_bound = left_proj + left_r * dir_norm
        right_bound = right_proj - right_r * dir_norm
        # If there's a gap between bounds, valid line exists
        if left_bound < right_bound:
            return True

        # Check for splits within duplicate projection groups (edge case)
        for m in range(1, n):
            if m != target_count:
                continue
            prev_proj, prev_r = projections[m-1]
            curr_proj, curr_r = projections[m]
            prev_bound = prev_proj + prev_r * dir_norm
            curr_bound = curr_proj - curr_r * dir_norm
            if prev_bound < curr_bound:
                return True

    # No valid split found in any critical direction
    return False

• Time Complexity: O(n² log n) — we iterate over O(n²) direction pairs, and sort O(n) projections per direction. This works well for sets up to ~1000 circles.
• Why Critical Directions?: Rotating a split line only changes the circle count on each side when it aligns with a perpendicular to a center pair. We don’t need to check random directions because all valid splits will align with one of these critical orientations.
• Non-Touching Guarantee: The problem’s constraint that circles don’t touch ensures that if two centers have the same projection, there’s enough space between them to draw a valid split line.

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