Determine Circle Intersection Status for Rendering Order

Scenario

Graphics engine must evaluate multiple pairs of circles to decide rendering order based on intersection.

Question

Given an array where each element contains two circles defined as (x1, y1, r1, x2, y2, r 2), return for every pair whether they intersect, touch, or are separate.

Hints

Compute center distance d; compare d with r1+r2 and |r1−r2|.

Classify Circle Pair Relationships

You are given an array of circle pairs. Each pair is represented as [x1, y1, r1, x2, y2, r2], where (x1, y1) and r1 define the first circle and (x2, y2) and r2 define the second circle. For each pair, return one of: "INTERSECT" (two intersection points or coincident circles), "TOUCH" (tangent internally or externally), or "SEPARATE" (no common points, including one strictly inside the other). If the circles coincide (same center and radius), consider them "INTERSECT". Return a list of strings in the same order as the input pairs.

Constraints

• 1 <= len(pairs) <= 200000
• Coordinates and radii are integers: -1e9 <= x, y <= 1e9, 0 <= r <= 1e9
• Use integer arithmetic (compare squared distances) to avoid floating-point error
• Output list length must equal input list length

Examples

Example 1

Input: pairs = [[0,0,2, 5,0,2], [0,0,3, 0,0,3]]
Output: ["SEPARATE", "INTERSECT"]

Explanation: Pair1: d=5, r1+r2=4 => SEPARATE. Pair2: same center and radius => INTERSECT (coincident).

Example 2

Input: pairs = [[0,0,2, 4,0,2], [0,0,3, 2,0,2], [0,0,1, 0,3,1]]
Output: ["TOUCH", "INTERSECT", "SEPARATE"]

Explanation: Pair1: d=4 equals r1+r2=4 => TOUCH (external). Pair2: |r1−r2|=1 < d=2 < r1+r2=5 => INTERSECT. Pair3: d=3 > r1+r2=2 => SEPARATE.

Hints

1. Compare squared center distance d2 with (r1+r2)^2 and (|r1−r2|)^2.
2. If d2 > (r1+r2)^2 or d2 < (|r1−r2|)^2, circles are SEPARATE.
3. If d2 equals one of those squared values, circles TOUCH.
4. If centers and radii are identical, treat as INTERSECT.

Approach

Use squared distances to avoid floating-point operations: let d2 be the squared distance between centers. Compare d2 with (r1+r2)^2 and (|r1−r2|)^2. If d2 is greater than (r1+r2)^2, circles are disjoint externally. If d2 is less than (|r1−r2|)^2, one lies strictly inside the other without touching; both cases are SEPARATE. If d2 equals either boundary, they TOUCH (tangent). Otherwise, they INTERSECT at two points. If centers and radii match exactly, treat as INTERSECT (coincident).

• Time complexity: O(n)
• Space complexity: O(1) extra (excluding output)