CF 105160I - 纠缠之圆

We are given two circles in the plane. Each circle is defined by its center coordinates and radius. For every test case, we need to count how many distinct straight lines exist such that the line is tangent to both circles at the same time.

codeforcescompetitive-programming

CF 105160I - \u7ea0\u7f20\u4e4b\u5706

Rating: -
Tags: -
Solve time: 50s
Verified: yes

Solution

Problem Understanding

We are given two circles in the plane. Each circle is defined by its center coordinates and radius. For every test case, we need to count how many distinct straight lines exist such that the line is tangent to both circles at the same time. If there are infinitely many such lines, we must output −1.

Geometrically, a line is valid if it touches each circle at exactly one point, without cutting through the interior. The same geometric line is counted only once even if it can be seen as coming from different “tangent configurations”.

The constraints are large in terms of test cases, up to 100000, while coordinates and radii are at most 10000. This immediately rules out any per-test geometric construction that enumerates candidate lines explicitly or performs intersection checks against all possible tangents. The solution must reduce each test case to a constant amount of arithmetic.

A subtle edge case arises when the two circles coincide. If both centers and radii are identical, then every tangent line of that circle is simultaneously tangent to both, which yields infinitely many valid lines. Another corner case appears when circles are nested or one is strictly inside the other without touching; in such cases, no common tangent line exists. A naive approach that only checks center distance against sum of radii often fails to distinguish external and internal tangency configurations correctly.

Approaches

A brute-force interpretation would try to construct all tangent lines to the first circle and then test each line against the second circle. A single circle has infinitely many tangent lines, so in practice one would discretize directions or attempt to enumerate tangents via angle sampling or slope parameterization. Even if we restrict ourselves to tangents defined by contact points, this still involves continuous parameters and solving quadratic equations per candidate direction. For each candidate line, verifying tangency to both circles requires distance computations and root checks, leading to at least O(K) work per test case for some large K. This is fundamentally infeasible under 100000 test cases.

The key observation is that any common tangent line to two circles must be one of four classical geometric types: it can be an external common tangent (touching both circles on the same side of the segment joining centers) or an internal common tangent (crossing the segment joining centers, touching opposite sides). Each type reduces to a distance condition between circle centers and radii.

Let the centers be A and B, with radii r1 and r2, and let d be the distance between centers. The existence of tangents depends only on comparing d with r1 + r2 and |r1 − r2|. This comes from shifting one circle into a point by expanding or shrinking the other along the normal direction of the tangent line. Each valid configuration corresponds to a specific geometric inequality, and the number of valid tangents is determined by how many of these configurations are possible.

Special degeneracies occur when circles coincide (infinitely many tangents), when they touch internally or externally (some tangent types collapse into a single line), or when one circle lies completely inside the other (no tangents).

Thus the entire problem reduces to classifying the relative position of two circles using only three quantities: center distance, sum of radii, and absolute difference of radii.

Approach Time Complexity Space Complexity Verdict
Brute Force (construct tangents) O(∞) per test O(1) Impossible
Geometry classification O(1) per test O(1) Accepted

Algorithm Walkthrough

For each test case, we compute the squared distance between centers to avoid floating-point errors. We then compare it with squared threshold values derived from radii.

  1. Read two circles (x1, y1, r1) and (x2, y2, r2). If the circles are identical in both center and radius, we output −1 because every tangent line of a single circle is valid for both.
  2. Compute dx = x1 − x2 and dy = y1 − y2, and define d2 = dx·dx + dy·dy. This represents the squared distance between centers.
  3. Compute sumR = r1 + r2 and diffR = |r1 − r2|. These values define the thresholds for external and internal tangency configurations.
  4. If d2 is zero but circles are not identical, the circles share the same center but have different radii. In this case, no line can be tangent to both since any tangent to one circle lies entirely outside the other concentric circle. We output 0.
  5. If d2 < diffR², one circle lies strictly inside the other without touching. No tangent line can touch both boundaries simultaneously, so we output 0.
  6. If d2 equals diffR², the circles are internally tangent. Exactly one internal common tangent exists.
  7. If d2 > diffR² and d2 < sumR², circles overlap. In this region, exactly two external common tangents exist.
  8. If d2 equals sumR², circles are externally tangent. In this case, three distinct common tangents exist: two external and one degenerate shared tangent.
  9. If d2 > sumR², circles are disjoint. All four classical common tangents exist.

Why it works

Every common tangent line is determined by a direction vector perpendicular to a radius at the tangency point. For a fixed line, shifting along its normal direction reduces the problem to comparing signed distances from centers to the line. The constraints imposed by tangency translate into linear equations in that signed distance. Solving these simultaneously for two circles leads exactly to the conditions involving d, r1, and r2. The number of solutions corresponds to how many consistent sign assignments are possible, which is precisely what the case analysis above enumerates. Since the classification depends only on relative distances, no geometric construction beyond these comparisons is required.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    out = []

    for _ in range(t):
        x1, y1, r1 = map(int, input().split())
        x2, y2, r2 = map(int, input().split())

        dx = x1 - x2
        dy = y1 - y2
        d2 = dx * dx + dy * dy

        if x1 == x2 and y1 == y2 and r1 == r2:
            out.append("-1")
            continue

        sumR = r1 + r2
        diffR = abs(r1 - r2)

        if d2 == 0:
            out.append("0")
        elif d2 < diffR * diffR:
            out.append("0")
        elif d2 == diffR * diffR:
            out.append("1")
        elif d2 < sumR * sumR:
            out.append("2")
        elif d2 == sumR * sumR:
            out.append("3")
        else:
            out.append("4")

    print("\n".join(out))

if __name__ == "__main__":
    solve()

The implementation mirrors the classification directly. The first guard handles the infinite case of identical circles. The squared distance is used throughout to avoid precision issues. Each subsequent branch corresponds exactly to a geometric regime defined by whether circles are nested, tangent, intersecting, or disjoint. The order of checks is important because equality cases must be separated before strict inequalities to avoid misclassification.

Worked Examples

Example 1

Input:

1
0 0 1
0 3 1

Here dx = 0, dy = −3, so d2 = 9. We have sumR = 2 and diffR = 0, so sumR² = 4 and diffR² = 0.

Step d2 diffR² sumR² Decision
Compute distance 9 0 4 disjoint case

Since d2 > sumR², the circles are separated and all four tangents exist, so the answer is 4.

This confirms the interpretation that sufficiently separated circles admit both internal and external tangent lines.

Example 2

Input:

1
0 0 2
3 0 1

Here dx = 3, dy = 0, so d2 = 9. We have sumR = 3, diffR = 1, so sumR² = 9 and diffR² = 1.

Step d2 diffR² sumR² Decision
Compare 9 1 9 external tangent

Since d2 == sumR², the circles are externally tangent, producing 3 common tangents.

This case shows the importance of equality handling: missing the equality branch would incorrectly classify this as disjoint or overlapping.

Complexity Analysis

Measure Complexity Explanation
Time O(T) Each test case performs constant-time arithmetic operations
Space O(1) Only a few variables are used regardless of input size

The solution scales linearly with the number of test cases, which is optimal given up to 100000 inputs. Each test case reduces to a fixed number of integer operations, well within limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from sys import stdout
    out = []
    
    t = int(input())
    for _ in range(t):
        x1, y1, r1 = map(int, input().split())
        x2, y2, r2 = map(int, input().split())

        dx = x1 - x2
        dy = y1 - y2
        d2 = dx*dx + dy*dy

        if x1 == x2 and y1 == y2 and r1 == r2:
            out.append("-1")
            continue

        sumR = r1 + r2
        diffR = abs(r1 - r2)

        if d2 == 0:
            out.append("0")
        elif d2 < diffR*diffR:
            out.append("0")
        elif d2 == diffR*diffR:
            out.append("1")
        elif d2 < sumR*sumR:
            out.append("2")
        elif d2 == sumR*sumR:
            out.append("3")
        else:
            out.append("4")

    return "\n".join(out)

# provided sample
assert run("""1
1 1 1
1 3 1
""") == "4"

# identical circles
assert run("""1
0 0 1
0 0 1
""") == "-1"

# concentric different radii
assert run("""1
0 0 5
0 0 2
""") == "0"

# externally tangent
assert run("""1
0 0 2
3 0 1
""") == "3"

# disjoint
assert run("""1
0 0 1
10 0 1
""") == "4"
Test input Expected output What it validates
identical circles -1 infinite tangent lines case
concentric different radii 0 no common tangent when same center
externally tangent 3 equality handling at sumR boundary
disjoint circles 4 full tangent set when far apart

Edge Cases

When the circles are identical, the algorithm triggers the first condition and outputs −1 immediately. For example, (0,0,1) and (0,0,1) are caught before any distance computation matters, correctly representing infinitely many shared tangents.

For concentric circles with different radii, such as (0,0,5) and (0,0,2), the squared distance is zero while diffR² is positive. The condition d2 < diffR² is triggered, producing 0. This matches the geometric fact that any tangent to one circle cannot touch the other concentric circle.

For externally tangent circles like (0,0,2) and (3,0,1), we get d2 == sumR². The equality branch ensures we return 3. A strict inequality-only implementation would misclassify this as disjoint, which would incorrectly output 4.

For disjoint circles such as (0,0,1) and (10,0,1), the distance condition exceeds sumR², placing the configuration in the final case with 4 tangents, reflecting the full set of external and internal tangent lines.