johnchen902's Blog

Fit two circles into a specified rectangle. The areas of the circles and the area of their intersection are also specified.

First, we need to find the distance between the circles meeting the "intersection area" constrain. It's too difficult for me to compute it directly, so I used binary search.

Second, we need to fit the circles into the specified rectangle. I only tried vertical and horizontal positions at first and got a Wrong Answer, as any angle may be a feasible position. Fortunately it's not hard to fit them properly.

#include <cstdio>
#include <cmath>
using namespace std;
constexpr double pi = acos(-1.0);
double func(double ra, double rb, double d) {
    double t1 = 2 * acos((ra * ra + d * d - rb * rb) / (2 * ra * d));
    double t2 = 2 * acos((rb * rb + d * d - ra * ra) / (2 * rb * d));
    return (ra * ra * (t1 - sin(t1)) + rb * rb * (t2 - sin(t2))) / 2;
}
double inverse(double ra, double rb, double c) {
    double l = abs(ra - rb), r = ra + rb;
    for(int i = 0; i < 100; i++) {
        double m = (l + r) / 2;
        double v = func(ra, rb, m);
        if(v > c) 
            l = m;
        else if(v < c)
            r = m;
        else
            return m;
    }
    return (l + r) / 2;
}
struct Swap {
    bool enabled;
    double &xa, &ya, &xb, &yb;
    ~Swap() {
        if(enabled) {
            swap(xa, xb);
            swap(ya, yb);
        }
    }
};
double mysqrt(double x) {
    return x <= 0 ? 0 : sqrt(x);
}
bool solve(double w, double h, double ra, double rb, double d,
        double &xa, double &ya, double &xb, double &yb) {
    // fprintf(stderr, "%f %f %f %f %f\n", w, h, ra, rb, d);
    Swap swapper { ra < rb, xa, ya, xb, yb };
    if(swapper.enabled)
        swap(ra, rb);
    if(w < 2 * ra || h < 2 * ra)
        return false;
    xa = ya = ra;
    if(w >= ra + d + rb) {
        xb = ra + d;
        yb = ra;
        return true;
    }
    xb = w - rb;
    yb = ya + mysqrt(d * d - (xb - xa) * (xb - xa));
    if(yb + rb <= h)
        return true;
    return false;
}
int main() {
    int w, h, a, b, c;
    while(true) {
        scanf("%d %d %d %d %d", &w, &h, &a, &b, &c);
        if(!w && !h && !a && !b && !c)
            break;
        double ra = sqrt(a / pi);
        double rb = sqrt(b / pi);
        double d = inverse(ra, rb, c);
        double xa = 0, ya = 0, xb = 0, yb = 0;
        if(solve(w, h, ra, rb, d, xa, ya, xb, yb)) {
            printf("%.9f %.9f %.9f %.9f %.9f %.9f\n",
                xa, ya, ra, xb, yb, rb);
        } else {
            puts("impossible");
        }
    }
}