So, solution is based on Descartes' theorem. We well work with radius, not diameter, and Curvature, with is 1/r
.
We will use double for all calculation, but if you work with significantly small numbers, I would prefer BigDecimal. It will slow algorithm, and you should use external method for finding square root, because BigDecimal doesn't have any.
For given D1, D2, minD we modify code above for efficiency:
Some preparation:
double D1 = sc.nextDouble() / 2;
double D2 = sc.nextDouble() / 2;
minD = sc.nextDouble() / 2;
double D3 = D1 + D2;
So, first step looks like this:
Next step looks a little bit more complicated.
Assume we want to write a recursion to solve this problem, and according to Descartes' theorem, for given curvatures of three circles, tangent to each other, (pic. below) , we could find curvatures of two circles, but for our purposes, we need only small one, so, we can simplify formula to
this.curve = a.curve + b.curve + c.curve + 2 * Math.sqrt(Math.abs(a.curve * b.curve + a.curve * c.curve + b.curve * c.curve));
Lets take a look at Apollonian gaskets again: try to play with it. See? It is same gaskets, but with different start condition. And whats more important for us, is that it is symmetrical! So, we will calculate just a half, and then multiply result by two! Lets write a recursion! Inputs will be curvatures of three circles. No output, we will use change our global variables.
double radius_sum = 0.0;
double square_radius_sum = 0.0;
void createAG(double a, double b, double c){
double n = a + b + c + Math.sqrt(a*b + a*c + b*c + 4.0);
if ((minD * n) < 1){
radius_sum += 2. / n; //Remember about symmetry?
square_radius_sum += 2. * (1. / n) * (1. / n); //Remember about symmetry?
createAG(a, b, n);
createAG(a, c, n);
createAG(b, c, n);
}
}
To find the result, we will use formulas to calculate area and perimeter of circle. Perimeter is length of circumference and equal to . Area is equal to , as you already know, because we already calculated it in previous step, otherwise we had to store every radius and do more calculations.
radius_sum = 2 * Math.Pi * radius_sum;
square_radius_sum = Math.Pi * square_radius_sum;
But we forget about our first two circles! Let's fix it!
radius_sum += D1*2 + D2*2;
square_radius_sum += D1*D1 + D2*D2;
radius_sum = 2 * Math.Pi * radius_sum;
square_radius_sum = Math.Pi * square_radius_sum;
And there is always a room for improvement. For example, to use IEEE 754 in better way, I assume you will use 1. / x
instead of 1 / x
.
Thank you!
P.S. Copyright! This task (text and first picture of Apollonian gasket) is created by teachers at CTU, for course ALG. Picture of formulas is from Wikipedia. Everything else is public domain, if not patented, registered e.t.c.