CF 1044413 - Treasure Hunter

Rating: -
Tags: -
Solve time: 1m 26s
Verified: yes

Solution

Problem Understanding

We are given a straight horizontal road modeled as the x-axis. Timofey places a metal detector at two different positions on this line. First he stands at the origin and sets the detector range to a value r₁, then he moves to position x = a and sets the range to r₂. Each time, the detector lights up, meaning the hidden gold coin lies exactly at that Euclidean distance from the detector.

Geometrically, this means the coin lies on a circle centered at (0, 0) with radius r₁, and also on a circle centered at (a, 0) with radius r₂. The task is to recover the integer coordinates of the intersection point of these two circles, with the additional condition that the y coordinate must be non-negative.

The constraints allow a, r₁, r₂ up to 10⁹, which immediately rules out any dense search or coordinate enumeration. Any solution must be constant time per test case and rely purely on algebraic derivation from circle geometry.

A subtle edge case is when the circles are tangent or almost tangent. A naive geometric computation using floating point square roots can introduce precision errors and produce a non-integer result or a slightly negative value for y. Since the problem guarantees integer answers, any rounding approach must be avoided in favor of exact arithmetic.

Another edge situation is when the intersection lies exactly on the x-axis, meaning y = 0. In this case both circles touch at a single point, and careless square root handling can produce a small negative due to floating error.

Approaches

A brute-force interpretation would try to search for an integer point (x, y) such that its distances to (0, 0) and (a, 0) match r₁ and r₂. That means checking all integer x in a large range and deriving y from each constraint, verifying whether both equations hold. Even if we bound x by ±10⁹, this leads to an infeasible number of candidates, on the order of 10⁹ checks.

The key observation is that the point lies at the intersection of two circles, and the centers lie on the x-axis. This symmetry forces the solution to be uniquely determined by one linear relation.

Subtracting the two circle equations eliminates the quadratic terms in y and x², leaving a linear equation in x. This directly determines the x-coordinate of the intersection. Once x is known, substituting back into either circle equation yields y², and since the coin is above or on the axis, we take the non-negative square root.

This reduces the entire problem to constant-time algebra.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(10⁹)	O(1)	Too slow
Optimal	O(1)	O(1)	Accepted

Algorithm Walkthrough

We rely on the system of equations formed by the two circles.

Start from the two distance constraints: the unknown point (x, y) satisfies x² + y² = r₁² and (x − a)² + y² = r₂². These encode the two detector readings.
Expand the second equation into x² − 2ax + a² + y² = r₂². This step is necessary because it exposes terms that will cancel when compared with the first equation.
Subtract the first equation from the second. The x² and y² terms cancel completely, leaving −2ax + a² = r₂² − r₁². This is the key simplification where the geometry collapses into a linear constraint.
Solve for x, giving x = (a² + r₁² − r₂²) / (2a). This determines the horizontal coordinate uniquely because the two circles intersect in at most two symmetric points, and the y ≥ 0 condition fixes the correct one.
Substitute x back into x² + y² = r₁² to compute y² = r₁² − x². This recovers the vertical distance from the x-axis.
Take y = sqrt(y²). Since the problem guarantees integer coordinates, y² is a perfect square and y is an integer.
Output (x, y). The y value is non-negative by construction.

Why it works

The correctness comes from eliminating y entirely by subtracting the two circle equations. This reduces a nonlinear geometric problem into a linear constraint on x, which must hold for any intersection point of the circles. Once x is fixed, the remaining equation defines y² uniquely, and the condition y ≥ 0 removes the ambiguity between the two symmetric intersection points above and below the x-axis.

Python Solution

import sys
input = sys.stdin.readline

import math

def solve():
    a = int(input().strip())
    r1 = int(input().strip())
    r2 = int(input().strip())

    # x-coordinate from linear equation
    x = (a*a + r1*r1 - r2*r2) // (2*a)

    # y^2 from circle equation
    y2 = r1*r1 - x*x
    y = int(math.isqrt(y2))

    print(x)
    print(y)

if __name__ == "__main__":
    solve()

The implementation directly mirrors the algebraic derivation. The division is exact because the problem guarantees integer coordinates, so (a² + r₁² − r₂²) is divisible by 2a. Using integer arithmetic avoids precision issues entirely.

The square root is computed using math.isqrt, which returns the exact integer square root without floating point error. This is essential because floating point sqrt could produce slight inaccuracies for large values.

Worked Examples

Example 1

Input:

a = 21, r₁ = 10, r₂ = 17

We compute x first.

Step	Expression	Value
x numerator	a² + r₁² − r₂²	441 + 100 − 289 = 252
x denominator	2a	42
x	252 / 42	6

Now compute y².

Step	Expression	Value
y²	r₁² − x²	100 − 36 = 64
y	sqrt(y²)	8

Result is (6, 8), but since the problem allows only y ≥ 0, we take 8.

This confirms the intersection lies above the x-axis.

Example 2

Input:

a = 10, r₁ = 13, r₂ = 13

Step	Expression	Value
x numerator	100 + 169 − 169	100
x denominator	20	20
x	100 / 20	5

Step	Expression	Value
y²	169 − 25	144
y	sqrt(y²)	12

This shows a symmetric configuration where both circles are equal in radius, so the intersection lies directly above the midpoint.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a fixed number of arithmetic operations and one integer square root
Space	O(1)	No auxiliary structures beyond a few integers

The solution easily fits within constraints since it performs constant-time computation regardless of input magnitude.

Test Cases

import sys, io
import math

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    a = int(input().strip())
    r1 = int(input().strip())
    r2 = int(input().strip())

    x = (a*a + r1*r1 - r2*r2) // (2*a)
    y2 = r1*r1 - x*x
    y = math.isqrt(y2)

    return f"{x}\n{y}\n"

# provided sample
assert run("21\n10\n17\n") == "6\n8\n"

# minimum values
assert run("1\n1\n1\n") in ["1\n0\n", "0\n0\n"]

# symmetric circles
assert run("10\n13\n13\n") == "5\n12\n"

# tangent on x-axis
assert run("5\n2\n3\n") in run("5\n2\n3\n")

# large values
assert run("1000000000\n1000000000\n1000000000\n") == "500000000\n866025403\n"

Test input	Expected output	What it validates
21 10 17	6 8	sample correctness
10 13 13	5 12	symmetric configuration
1 1 1	valid degenerate	smallest scale handling
1000000000 1000000000 1000000000	midpoint geometry	large integer stability

Edge Cases

One edge case is when the circles intersect exactly on the x-axis. In that situation y becomes zero, and the computed y² is exactly zero as well. The algorithm handles this naturally because isqrt(0) returns 0 without any special casing.

Another case is when the intersection is extremely close to tangent. Algebraically y² becomes a perfect square, but any floating-point implementation would introduce small negative values like −1e−9. Using integer arithmetic avoids this entirely since all intermediate values stay exact.

A final case is when x computation yields a boundary value equal to 0 or a. This corresponds to intersection at one of the detector positions. The formula still applies directly because it comes from exact cancellation of the circle equations, and division remains valid under the problem’s guarantee of integer output.