AOJ 2572 Venn Diagram

解法

頑張って実装するだけ.
円の半径は入力からすぐわかる.
2つの円の距離を二分探索で求めたら,でかい方を左下隅に配置.
小さいほうは [0, pi/2] でどの角度に置くとよいかを判定.計算したくないので二分探索もどきでサボる.
最後にはみ出ないか確認して終わり.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ld = long double;
using point = complex<ld>;

constexpr ld eps = 1e-5;
constexpr ld pi = acos(-1.0);

struct circle {
    circle(point p, ld r) : p(p), r(r) {}
    point p;
    ld r;
};

vector<point> is_cc(circle const& c1, circle const& c2) {
    vector<point> res;
    ld d = abs(c1.p - c2.p);
    ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
    ld dfr = c1.r * c1.r - rc * rc;
    if(abs(dfr) < eps) {
        dfr = 0;
    } else if(dfr < 0) {
        return res;
    }

    ld rs = sqrt(dfr);
    point diff = (c2.p - c1.p) / d;
    res.push_back(c1.p + diff * point(rc, rs));
    if(dfr != 0) {
        res.push_back(c1.p + diff * point(rc, -rs));
    }
    return res;
}

// assert: c1 is left position
ld intersect_area(circle c1, circle c2) {
    const ld d = abs(c1.p - c2.p);
    if(d >= c1.r + c2.r - eps) return 0;
    if(c1.r < c2.r) swap(c1.r, c2.r);
    if(d < eps) return (c2.r * c2.r * pi);

    auto ps = is_cc(c1, c2);
    assert(!ps.empty());

    ld rad1 = abs(arg(ps[0] - c1.p));
    ld S = c1.r * c1.r * rad1 - 0.5 * c1.r * c1.r * sin(2 * rad1);
    ld rad2 = pi - abs(arg(ps[0] - c2.p));
    S += c2.r * c2.r * rad2 - 0.5 * c2.r * c2.r * sin(2 * rad2);
    return S;
}

int main() {
    cout << fixed << setprecision(10);

    ld w, h, a, b, ab;
    while(cin >> w >> h >> a >> b >> ab) {
        if(w == 0) break;

        const ld ra = sqrt(a / pi);
        const ld rb = sqrt(b / pi);

        if(min(w, h) < ra * 2 || min(w, h) < rb * 2) {
            cout << "impossible" << endl;
            continue;
        }

        circle c1(point(0, 0), ra);
        ld d = 0;
        { // calc dist
            ld lb = abs(ra - rb), ub = ra + rb;
            for(int loop = 0; loop < 100; ++loop) {
                const ld mid = (ub + lb) / 2;
                circle c2(point(mid, 0), rb);
                if(intersect_area(c1, c2) + eps < ab) {
                    ub = mid;
                } else {
                    lb = mid;
                }
            }

            d = lb;
        }
        // check
        bool swapped = ra < rb;
        c1.r = swapped ? rb : ra;
        c1.p = point(c1.r, c1.r);
        circle c2(point(c1.r + d, c1.r), swapped ? ra : rb);
        assert(abs(intersect_area(c1, c2) - ab) < 2 * eps);
        {
            ld lb = 0, ub = pi / 2;
            for(int loop = 0; loop < 60; ++loop) {
                const ld mid = (lb + ub) / 2;
                c2.p = c1.p + point(cos(mid) * d, sin(mid) * d);
                if(imag(c2.p) + c2.r > h + eps || real(c2.p) - c2.r < -eps) {
                    ub = mid;
                } else if(real(c2.p) + c2.r > w + eps || imag(c2.p) - c2.r < -eps) {
                    lb = mid;
                } else {
                    break;
                }
            }
        }

        if(imag(c2.p) + c2.r <= h + eps && real(c2.p) + c2.r <= w + eps
           && imag(c2.p) - c2.r >= -eps && real(c2.p) - c2.r >= -eps) {
            if(swapped) swap(c1, c2);
            cout << real(c1.p) << ' ' << imag(c1.p) << ' ' << c1.r << ' ';
            cout << real(c2.p) << ' ' << imag(c2.p) << ' ' << c2.r << endl;
        } else {
            cout << "impossible" << endl;
        }
    }
}

感想

こういうのを15分ぐらいで通せるようにならないとなあという感じ.