当前位置:首页 » Project Euler » 详细页

Iterative Circle Packing 题号:199 难度: 70 中英对照

Three circles of equal radius are placed inside a larger circle such that each pair of circles is tangent to one another and the inner circles do not overlap. There are four uncovered "gaps" which are to be filled iteratively with more tangent circles.

At each iteration, a maximally sized circle is placed in each gap, which creates more gaps for the next iteration. After 3 iterations (pictured), there are 108 gaps and the fraction of the area which is not covered by circles is 0.06790342, rounded to eight decimal places.

What fraction of the area is not covered by circles after 10 iterations?
Give your answer rounded to eight decimal places using the format x.xxxxxxxx .


Solution

根据论文《三个两两相外切圆的内公切圆与外公切圆》,四个圆两两相切的情况下,四个圆的曲率(半径的倒数)记为$a,b,c,d$,则满足关系式: $$2\left( a^2+b^2+c^2+d^2\right) =\left( a+b+c+d\right) ^2$$ 根据上式求解$d$,有: $$d=a+b+c+2\sqrt{ab+bc+ac}$$ 于是迭代求解即可。

Code


public final class p199 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }


    static public String run() {
		int size = 10;
		double k1 = 1; // choose curvature 1 for the 3 equal circles
		double k0 = k1 * (3 - 2 * Math.sqrt(3)); // get curvature of the outer
													// circle
		double a0 = 1 / (k0 * k0); // area of outer circle
		double a1 = 3 / (k1 * k1); // area of 3 inner circles
		a1 += 3 * getArea(k0, k1, k1, size); // fill three outer gaps
		a1 += getArea(k1, k1, k1, size); // fill centre gap
		return String.format("%.6g", ((a0 - a1) / a0));
	}


	static double getArea(double k1, double k2, double k3, int depth) {
		if (depth == 0)
			return 0.0;
		// calculate circle curvature of inside circle
		double k4 = k1 + k2 + k3 + 2 * Math.sqrt(k1 * k2 + k2 * k3 + k3 * k1);
		double a = 1 / (k4 * k4); // circle area
		a += getArea(k1, k2, k4, depth - 1); // add areas if inbetween fillings
		a += getArea(k2, k3, k4, depth - 1);
		a += getArea(k3, k1, k4, depth - 1);
		return a;
	}

}
0.00396087
51ms