Description

Hans wants to become a glass carver (a person who creates beautiful artwork by cutting the glass). He already has a rectangular piece of glass of size w  h millimeters, a diamond glass cutter and lots of enthusiasm. What he lacks is understanding of what to carve and how. In order not to waste time, he decided to PRactice the technique of carving. To do this, he makes vertical and horizontal cuts through the entire sheet. This process results in making smaller rectangular fragments of glass. Hans does not move the newly made glass fragments. In particular, a cut divides each fragment of glass that it goes through into smaller fragments. Hans doesn’t know how to make a great artwork, so he performs random cuts as follows. First, he tosses a fair coin to determine if he is going to cut the glass vertically or horizontally (that is, the probability of choosing each direction is 50%). After that, he chooses a uniformly distributed random real point on the corresponding side of the rectangle, and makes a cut through that point.All n random points and all n coin tosses are mutually independent. Hans is going to perform exactly n cuts. What he is interested in, is the fragment with the smallest area that is formed after he makes all cuts. Denote its area as ξ$/xi$. Your task is to calculate E[ξ]$E[/xi]$, the expected value of ξ$/xi$.

Input

The only line of input contains three space-separated integers w, h and n (1≤w,h≤103,1≤n≤106$1/le w, h/le 10^3, 1/le n /le 10^6$), the size of the piece of glass and the number of cuts Hans is going to perform.

Output

Output the expected area of the smallest fragment formed after performing all cuts. Your answer will be considered correct if its relative error is no more than 10?4$10^{-4}$ (note that having absolute error no more that 10?4$10^{-4}$ is not enough).

題意

對給定的 h×w$h/times w$ 的矩形在等概率的情況下任意橫切或縱切 n 下，將矩形分為若干塊，其中計最小一塊的面積為 ξ$/xi$ ，試求最小面積的期望 E[ξ]$E[/xi]$ 。

分析

期望公式： E[ξ]=Σni=0Cin2n(i+1)2(n?i+1)2 $$E[/xi] = /Sigma_{i=0}^{n}/frac{C_n^i}{2^n(i+1)^2(n-i+1)^2}$$ ?膜拜隊友大神，給出期望公式 :haha:

T_T 然而此題不止一個坑點。顯然計算 2n$2^n$ 當 n=1000000 時，各種數(shù)據(jù)類型都已經(jīng)無法表示。但套用 log 和 exp 的策略可解決這個問題。因此，對期望公式加以轉(zhuǎn)換： E[ξ]=Σni=0elnCin?(nln2+2ln(i+1)+2ln(n?i+1)) $$E[/xi] = /Sigma_{i=0}^{n} e^{/ln{C_n^i}-(n/ln{2}+2/ln{(i+1)}+2/ln{(n-i+1)})}$$ 貌似非常卡精度，全部用 long double 。

代碼