Educational Codeforces Round 2 D. Area of Two Circles' Intersection

問題

codeforces.com

解法

アイデアだけなら大学受験の典型ですね(手計算でとけるかは置いておいて)

2 つの円の半径を r, R (r <= R), 2 つの円の距離を d とします。

• R+r <= d なら, 円は交わらないので答えは 0
• R-r >= d なら, 円 r は 円 R に完全に含まれるので, 答えは pi*r^2
• それ以外の場合は, 辺の長さがそれぞれ R, r, d の三角形が中に出来て, 辺 r に対する角度 phi と, 辺 R に対する角度 theta が, 余弦定理によってわかります。これが分かれば, 交わっている部分の面積は, ２つの「扇型 - 三角形」の形で書けるので, 面積を求められます。

Real add(Real a, Real b) {
    if (abs(a+b) < eps * (abs(a)+abs(b))) return 0;
    return a+b;
}

bool equal(Real a, Real b) {
    return add(a, -b) == 0;
}
struct P {
    Real x, y;
    P() {}
    P(Real x, Real y) : x(x), y(y) {}
    P operator+(P p) const {return P(add(x, p.x), add(y, p.y));}
    P operator-(P p) const {return P(add(x, -p.x), add(y, -p.y));}
    P operator*(Real d) const {return P(x*d, y*d);}
    Real dot(P p) const {return add(x*p.x, y*p.y);} // 内積
    Real det(P p) const {return add(x*p.y, -y*p.x);} // 外積
    Real dist(P p) const {return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));} // 距離
    void normalize() {Real d = sqrt(x*x+y*y); x /= d; y /= d;} // 正規化
    bool operator<(const P& rhs) const {
        if (x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
    bool operator==(const P& rhs) const {
        return equal(x, rhs.x) && equal(y, rhs.y);
    }
};

const Real pi = acosl(-1);
Real square(Real x) {return x*x;}

Real calc(Real r, Real theta) {
    Real ret = r*r*theta;
    ret -= 2*(r*sinl(theta)) * (r*cosl(theta)) / 2;
    return ret;
}

int main() {
    Real x1, y1, R;
    Real x2, y2, r;
    cin >> x1 >> y1 >> R;
    cin >> x2 >> y2 >> r;
    P p1(x1, y1), p2(x2, y2);
    if (R < r) {
        swap(R, r);
        swap(p1, p2);
    }
    Real d = p1.dist(p2);
    Real ans;
    if (d >= R+r) {
        ans = 0;
    } else if (R >= d+r) {
        ans = r*r*pi;
    } else {
        Real theta = acosl((R*R+d*d-r*r)/(2*R*d));
        Real phi = acosl((r*r+d*d-R*R)/(2*r*d));
        ans = calc(R, theta);
        ans += calc(r, phi);
    }
    cout << setprecision(12) << ans << endl;
    return 0;
}