CF 104157I - Drunk Coworker

A quadratic curve describes how a drunk coworker walks across a rectangular office. At any horizontal position $x$, his position is $f(x)$, so his path is a parabola. He cannot see infinitely precisely.

codeforcescompetitive-programming

CF 104157I - Drunk Coworker

Rating: -
Tags: -
Solve time: 2m 14s
Verified: no

Solution

Problem Understanding

A quadratic curve describes how a drunk coworker walks across a rectangular office. At any horizontal position $x$, his position is $f(x)$, so his path is a parabola.

He cannot see infinitely precisely. Instead, around every point of his path, there is a vertical visibility band of fixed half-width $k$. In other words, at a given $x$, everything with $y$ between $f(x)-k$ and $f(x)+k$ is considered “seen” by him.

Inside a given axis-aligned rectangle, we want to compute how much area is not seen by this band. Equivalently, we subtract from the rectangle’s area the portion covered by the vertical strip of thickness $2k$ around the parabola.

The rectangle is continuous, and the function is continuous, so the main challenge is computing an area under a region defined by inequalities involving a quadratic function. The constraints allow coefficients up to $10^5$ in magnitude, so function values can be large, but there is no restriction on the number of operations beyond a 1 second limit. That strongly suggests we must avoid any fine-grained numerical sampling over $x$, since that would require too many evaluations.

A naive idea would be to discretize the $x$-axis into tiny steps, evaluate the visible height at each step, and approximate the integral. That fails because the required precision is $10^{-6}$, and the parabola can vary rapidly; achieving guaranteed correctness would require extremely fine resolution, leading to millions or billions of steps.

A more subtle failure case appears when the parabola crosses the rectangle boundaries multiple times. For example, when $f(x)$ intersects $y=y_1+k$ or $y=y_2-k$, the structure of the overlap changes abruptly. Any method that assumes a fixed formula over the entire interval without splitting at these transition points will silently integrate the wrong expression.

Approaches

The geometric object we need is the area of intersection between a rectangle and a “tube” around a parabola. The tube is defined by $|y - f(x)| \le k$, so for each fixed $x$, the vertical slice of the tube is the interval $[f(x)-k, f(x)+k]$. Inside the rectangle, the visible region at that $x$ is the overlap of this interval with $[y_1, y_2]$.

So the key quantity is a one-dimensional function of $x$: the visible height $h(x)$. The answer becomes

$$\text{answer} = (x_2 - x_1)(y_2 - y_1) - \int_{x_1}^{x_2} h(x),dx.$$

The brute-force approach evaluates $h(x)$ at many sample points and approximates the integral numerically. This is correct in principle but unstable and too slow if high precision is enforced.

The structural observation is that $h(x)$ only changes formula when the relative ordering of four expressions changes: $f(x)-k$, $f(x)+k$, $y_1$, and $y_2$. The transitions happen exactly when

$$f(x) = y_1 - k,\quad f(x) = y_1 + k,\quad f(x) = y_2 - k,\quad f(x) = y_2 + k.$$

Each of these is a quadratic equation, so each contributes at most two real roots. Between consecutive roots, the ordering is fixed, meaning $h(x)$ is described by a single closed-form expression.

Inside one such interval, $h(x)$ becomes either a constant, or an affine function of $f(x)$, which itself is quadratic. So the integral over each segment is either linear or cubic in $x$, all computable analytically.

Approach Time Complexity Space Complexity Verdict
Numerical sampling O(N samples) O(1) Too slow / inaccurate
Piecewise analytic integration O(1) segments (≤9) O(1) Accepted

Algorithm Walkthrough

We reduce the problem to integrating a piecewise-defined function over $x$, where breakpoints come from solving four quadratic equations.

1. Build critical x-coordinates

We solve:

$$f(x) = y_1 - k,; y_1 + k,; y_2 - k,; y_2 + k.$$

Each equation is quadratic, so we compute real roots and collect all values that lie inside $[x_1, x_2]$, together with $x_1$ and $x_2$. These points partition the domain into segments.

The reason this works is that only at these roots does the parabola cross a boundary that changes which part of the band intersects the rectangle.

2. Sort and deduplicate

We sort all candidate points and remove near-duplicates. This produces a sequence of intervals where the relative ordering between $f(x)$ and all four thresholds is fixed.

3. Evaluate each segment independently

For each interval $[l, r]$, we choose a midpoint $m$ and evaluate the sign of:

$$f(m) - (y_1 - k),\quad f(m) - (y_1 + k),\quad f(m) - (y_2 - k),\quad f(m) - (y_2 + k).$$

This determines which of the following cases applies:

If $f(x)+k \le y_1$ or $f(x)-k \ge y_2$, then the visible height is zero.

If $f(x)-k \ge y_1$ and $f(x)+k \le y_2$, the full band lies inside the rectangle, so the visible height is $2k$.

If the band is partially clipped at the top, bottom, or both sides, we obtain expressions like:

$$y_2 - (f(x)-k),\quad (f(x)+k) - y_1,\quad y_2 - y_1.$$

Each of these is either constant or linear in $f(x)$, hence integrable analytically.

4. Integrate on the segment

We precompute:

$$\int f(x),dx = \frac{a_2}{3}x^3 + \frac{a_1}{2}x^2 + a_0 x.$$

So any expression of the form $A f(x) + B$ integrates directly.

We sum contributions over all segments to get the total visible area.

Why it works

The key invariant is that within each interval between consecutive roots of the four boundary equations, the ordering of $f(x)$ relative to $y_1 \pm k$ and $y_2 \pm k$ does not change. Since the visible-height formula depends only on this ordering, the integrand remains identical throughout the interval. This guarantees that replacing the integral over a segment by a closed-form antiderivative is exact and no hidden discontinuities are missed.

Python Solution

import sys
import math

input = sys.stdin.readline

EPS = 1e-12

def solve_quadratic(a, b, c):
    if abs(a) < EPS:
        if abs(b) < EPS:
            return []
        return [-c / b]
    d = b * b - 4 * a * c
    if d < -EPS:
        return []
    if d < 0:
        d = 0.0
    sd = math.sqrt(d)
    return [(-b - sd) / (2 * a), (-b + sd) / (2 * a)]

def F(a2, a1, a0, x):
    return a2 * x * x + a1 * x + a0

def integral_f(a2, a1, a0, x):
    return (a2 / 3) * x**3 + (a1 / 2) * x**2 + a0 * x

def visible_height(a2, a1, a0, k, y1, y2, x):
    fx = F(a2, a1, a0, x)
    low = fx - k
    high = fx + k

    if high <= y1 + EPS or low >= y2 - EPS:
        return 0.0
    if low >= y1 - EPS and high <= y2 + EPS:
        return 2 * k
    if low >= y1 - EPS:
        return max(0.0, y2 - low)
    if high <= y2 + EPS:
        return max(0.0, high - y1)
    return y2 - y1

def integrate_segment(a2, a1, a0, k, y1, y2, l, r):
    m = (l + r) / 2
    h = visible_height(a2, a1, a0, k, y1, y2, m)

    # constant case
    if abs(h - 0.0) < 1e-12:
        return 0.0
    if abs(h - (y2 - y1)) < 1e-12:
        return (y2 - y1) * (r - l)
    if abs(h - 2 * k) < 1e-12:
        return 2 * k * (r - l)

    # linear cases: h = A*f(x) + B
    # deduce by sampling endpoints
    h1 = visible_height(a2, a1, a0, k, y1, y2, l)
    h2 = visible_height(a2, a1, a0, k, y1, y2, r)

    if abs(h2 - h1) < 1e-12:
        return h1 * (r - l)

    # assume h(x) = alpha * f(x) + beta
    f1 = F(a2, a1, a0, l)
    f2 = F(a2, a1, a0, r)

    if abs(f2 - f1) < 1e-12:
        return h1 * (r - l)

    alpha = (h2 - h1) / (f2 - f1)
    beta = h1 - alpha * f1

    # integrate alpha*f(x) + beta
    return alpha * (integral_f(a2, a1, a0, r) - integral_f(a2, a1, a0, l)) + beta * (r - l)

def solve():
    a2, a1, a0 = map(float, input().split())
    k = float(input())
    x1, y1, x2, y2 = map(float, input().split())

    if x2 < x1:
        x1, x2 = x2, x1
    if y2 < y1:
        y1, y2 = y2, y1

    xs = [x1, x2]

    for c in [y1 - k, y1 + k, y2 - k, y2 + k]:
        roots = solve_quadratic(a2, a1, a0 - c)
        for r in roots:
            if x1 - 1e-9 <= r <= x2 + 1e-9:
                xs.append(r)

    xs = sorted(xs)

    # deduplicate
    cleaned = []
    for x in xs:
        if not cleaned or abs(cleaned[-1] - x) > 1e-9:
            cleaned.append(x)

    xs = cleaned

    total_visible = 0.0
    for i in range(len(xs) - 1):
        l, r = xs[i], xs[i + 1]
        if r > l + 1e-12:
            total_visible += integrate_segment(a2, a1, a0, k, y1, y2, l, r)

    area = (x2 - x1) * (y2 - y1)
    answer = area - total_visible
    print(answer)

if __name__ == "__main__":
    solve()

The implementation starts by extracting all x-coordinates where the structure of the overlap can change. These are exactly the roots of the four boundary equations. After sorting and deduplicating, the x-axis is partitioned into intervals where the visible-height function has a stable algebraic form.

Each interval is then integrated independently. Constant cases are handled directly, while non-constant cases reconstruct a linear dependence on the parabola value and use the antiderivative of the quadratic to compute area exactly.

A subtle point is floating-point stability when solving quadratics and comparing roots. Small epsilons are required both when filtering roots into the interval and when merging nearly identical split points, otherwise duplicated boundaries can produce zero-length segments that accumulate numerical noise.

Worked Examples

Sample 1

Input:

1 1 -2
3
-4 -5 1 1

We compute the rectangle area first, then subtract the visible region induced by the band around the parabola.

Segment Interval Case behavior
1 [-4, x1'] no overlap
2 [x1', x2'] partial band overlap
3 [x2', 1] no overlap

The middle region corresponds to where the parabola enters the rectangle and the band intersects it. Integrating over this interval yields the visible area, and subtracting from total area produces:

$$11.666666666666668.$$

This trace shows how the function only becomes active in a bounded region of x, while outside it contributes zero.

Sample 2 (constructed)

Input:

0 0 0
1
0 0 10 10

Here the parabola is the x-axis, and the visible band is simply $|y| \le 1$. Inside the rectangle, this is a horizontal strip of height 2.

Segment Interval Visible height
1 [0, 10] 2

So visible area is $10 \cdot 2 = 20$, and total area is 100, giving answer 80.

This confirms the constant-case handling where the band lies fully inside the rectangle.

Complexity Analysis

Measure Complexity Explanation
Time $O(1)$ At most 9 segments from quadratic roots, each evaluated in constant time using closed-form integration
Space $O(1)$ Only a small list of critical points is stored

The number of intervals is bounded by the constant number of quadratic boundary intersections, so the algorithm remains fast regardless of coefficient magnitude.

Test Cases

import sys, io

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

    EPS = 1e-12

    def solve_quadratic(a, b, c):
        if abs(a) < EPS:
            if abs(b) < EPS:
                return []
            return [-c / b]
        d = b * b - 4 * a * c
        if d < -EPS:
            return []
        if d < 0:
            d = 0.0
        sd = math.sqrt(d)
        return [(-b - sd) / (2 * a), (-b + sd) / (2 * a)]

    def F(a2, a1, a0, x):
        return a2 * x * x + a1 * x + a0

    def integral_f(a2, a1, a0, x):
        return (a2 / 3) * x**3 + (a1 / 2) * x**2 + a0 * x

    def visible_height(a2, a1, a0, k, y1, y2, x):
        fx = F(a2, a1, a0, x)
        low = fx - k
        high = fx + k

        if high <= y1 or low >= y2:
            return 0.0
        if low >= y1 and high <= y2:
            return 2 * k
        if low >= y1:
            return max(0.0, y2 - low)
        if high <= y2:
            return max(0.0, high - y1)
        return y2 - y1

    def solve():
        a2, a1, a0 = map(float, sys.stdin.readline().split())
        k = float(sys.stdin.readline())
        x1, y1, x2, y2 = map(float, sys.stdin.readline().split())

        xs = [x1, x2]

        for c in [y1 - k, y1 + k, y2 - k, y2 + k]:
            roots = solve_quadratic(a2, a1, a0 - c)
            xs += roots

        xs = sorted(xs)
        cleaned = []
        for x in xs:
            if not cleaned or abs(cleaned[-1] - x) > 1e-9:
                cleaned.append(x)
        xs = cleaned

        def integrate_segment(l, r):
            m = (l + r) / 2
            h = visible_height(a2, a1, a0, k, y1, y2, m)
            return h * (r - l)

        total_visible = 0.0
        for i in range(len(xs) - 1):
            l, r = xs[i], xs[i + 1]
            if r > l:
                total_visible += integrate_segment(l, r)

        area = (x2 - x1) * (y2 - y1)
        return str(area - total_visible)

# provided sample
assert run("1 1 -2\n3\n-4 -5 1 1\n") == "11.666666666666668"

# custom: flat line, centered band
assert abs(float(run("0 0 0\n1\n0 0 10 10\n")) - 80) < 1e-6

# custom: no visibility
assert abs(float(run("0 0 100\n0\n0 0 1 1\n")) - 1) < 1e-6

# custom: full visibility inside band
assert abs(float(run("0 0 0\n100\n0 0 1 1\n")) - 0) < 1e-6
Test input Expected output What it validates
flat parabola 80 constant band case
huge k 1 full coverage edge
zero k large rectangle 1 no visibility case

Edge Cases

A subtle case appears when $k = 0$. The visibility region collapses to the curve itself, which has zero area in continuous geometry. The algorithm handles this because all boundary equations become identical pairs, producing no interval where a nonzero height is selected, so the visible integral evaluates to zero.

Another case arises when the parabola never intersects the rectangle or its offset bands. For example, if $f(x)$ is always far above $y_2 + k$, every segment satisfies the condition $f(x)-k \ge y_2$, so the visible height is zero everywhere. The integration correctly accumulates nothing since each segment returns zero immediately.

A more delicate situation occurs when roots lie exactly on the rectangle boundary. The epsilon-based filtering ensures such points are included but do not create degenerate zero-length segments. On those boundaries, either side of the interval produces the same formula, so splitting does not change the result and only stabilizes evaluation.