BOJ. Two Circles (7869)

On this page

[Link] https://www.acmicpc.net/problem/7869

Intersection area

Let the circle centers be $C_1=(x_1,y_1)$ and $C_2=(x_2,y_2)$, their radii be $r_1,r_2$, and the distance between centers be $d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$. The intersection area depends on how the circles meet:

• If $d\ge r_1+r_2$, they are disjoint or externally tangent, so the intersection area is $0$.
• If $d\le |r_1-r_2|$, one circle lies inside the other or they are internally tangent. The intersection is the smaller disk, with area $\pi\min(r_1,r_2)^2$. This also handles coincident centers ($d=0$), including equal circles, without dividing by $d$.
• Otherwise, the circles partially overlap and their boundaries intersect at two points.

For partial overlap, draw radii to either intersection point. In the triangle formed by the two centers and that point, the cosine law gives the half-angles at the centers:

$$\theta_1=\cos^{-1}\left(\frac{d^2+r_1^2-r_2^2}{2dr_1}\right),\qquad \theta_2=\cos^{-1}\left(\frac{d^2+r_2^2-r_1^2}{2dr_2}\right).$$

Each circle contributes a sector with central angle $2\theta_i$. Subtracting the isosceles triangle inside that sector leaves a circular segment of area $r_i^2\theta_i-\frac12r_i^2\sin(2\theta_i)$. Adding the two segments gives the lens area:

$$A=r_1^2\theta_1+r_2^2\theta_2 -\frac12r_1^2\sin(2\theta_1)-\frac12r_2^2\sin(2\theta_2).$$

Floating-point rounding can move a cosine-law value slightly outside its mathematical range, so clamp each acos argument to [-1, 1]. The containment and disjointness cases are tested first; consequently the partial-overlap formulas never divide by zero and tangencies are handled by the boundary cases.

C++17 implementation

The algorithm uses constant time and constant extra space, $O(1)$ for both.

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    double x1, y1, r1, x2, y2, r2;
    std::cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;

    const double dx = x1 - x2;
    const double dy = y1 - y2;
    const double d = std::hypot(dx, dy);
    const double pi = std::acos(-1.0);
    double area;

    if (d >= r1 + r2) {
        area = 0.0;
    } else if (d <= std::abs(r1 - r2)) {
        const double radius = std::min(r1, r2);
        area = pi * radius * radius;
    } else {
        const double d2 = d * d;
        const double r1_2 = r1 * r1;
        const double r2_2 = r2 * r2;
        const double cos1 = std::clamp((d2 + r1_2 - r2_2) / (2.0 * d * r1), -1.0, 1.0);
        const double cos2 = std::clamp((d2 + r2_2 - r1_2) / (2.0 * d * r2), -1.0, 1.0);
        const double theta1 = std::acos(cos1);
        const double theta2 = std::acos(cos2);

        area = r1_2 * theta1 + r2_2 * theta2
             - 0.5 * r1_2 * std::sin(2.0 * theta1)
             - 0.5 * r2_2 * std::sin(2.0 * theta2);
    }

    std::cout << std::fixed << std::setprecision(3) << area << '\n';
    return 0;
}