问题描述

在一个有名的园游会中有这样的一个游戏，将一个硬币投掷到一个被一些正方形方格分割的桌子上。游戏的奖励取决于你投掷的硬币覆盖的方格数，覆盖的方格越多，奖励越高。

下图所示为一种投掷了5枚硬币的情形，图中的1号硬币覆盖了1个方格；2号硬币覆盖了2个方格；3号硬币覆盖了3个方格；4号方格覆盖了4个方格；5号硬币覆盖了2个方格。注意：硬币是可以跨越桌子的边界（图中的硬币5）。定义硬币覆盖一个方格指的是硬币与方格相交的面积为正，只与某方格边界相切的情况不被认为覆盖了该方格。你可以假定你投掷的硬币一定能够平躺在桌面上，你可以使你的硬币的圆心等概率地落在桌子上（包括桌子的边界）。

硬币覆盖特定数目方格的概率取决于方格的边长，硬币的大小，方格的数目。现在请你写一个程序来根据给定的数据计算硬币覆盖特定数目方格的概率。

输入格式

输入文件第一行包括一个整数，表示测试数据的组数。

对于每一组数据，包括4个整数，m，n，t，c，表示桌子上有m行n列方格，每个方格的边长是t，直径为c。

输出格式

对于每一组输出，首先输出测试数据的组数，接着分4行输出硬币覆盖1，2，3，4个方格的概率，保留4位小数，格式参见样例。

每两组数据之间输出一个空行，最后一组数据之后请不要输出多余的空行。

样例

3
5 5 10 3
7 4 25 20
10 10 10 4

Case 1:
Probability of covering 1 tile =57.7600%
Probability of covering 2 tiles=36.4800%
Probability of covering 3 tiles=1.2361%
Probability of covering 4 tiles=4.5239%

Case 2:
Probability of covering 1 tile =12.5714%
Probability of covering 2 tiles=46.2857%
Probability of covering 3 tiles=8.8293%
Probability of covering 4 tiles=32.3135%

Case 3:
Probability of covering 1 tile =40.9600%
Probability of covering 2 tiles=46.0800%
Probability of covering 3 tiles=2.7812%
Probability of covering 4 tiles=10.1788%

数据范围

$1≤m，n≤5000，1≤c<t≤1000$

来源

• POJ3440
• 信息学奥赛之数学一本通
• stong9070整理