I-Fishes

题目描述

当 Grisha 和 Ded Moroz 一起庆祝新年时，Misha 送给 Sasha 一个 $n\times m$ 大小的小型长方形池塘，池塘被划分为 $1\times 1$ 的格子，每个格子里住着一条邪恶的小鱼（每个格子最多只能有一条鱼，否则它们之间会打架！）。

礼包里还附带了一个边长为 $r$ 的正方形渔网（$r\times r$），用来捕鱼。如果你将渔网的左下角放在格子 $(x, y)$，则渔网覆盖的正方形区域 $(x, y)...(x+r-1, y+r-1)$ 里的所有小鱼会被捕获。需要注意的是，使用时渔网必须完全位于池塘内部。

遗憾的是，Sasha 捕鱼技术不高，所以她会随机把渔网撒下。为了不让 Sasha 沮丧，Misha 决定将 $k$ 条小鱼放进空池塘，并选择放置的格子，使得被捕获小鱼数量的期望尽可能大。现在请你帮助 Misha，找出这 $k$ 条鱼的最佳放置方案。换句话说，就是将 $k$ 条小鱼分别放到池塘的不同格子里，使得渔网在所有 $(n-r+1)\cdot(m-r+1)$ 种不同可覆盖位置中随机选择一个，平均能捕到的小鱼数最大。

输入格式

输入一行包含四个整数 $n, m, r, k$（$1 \leq n, m \leq 10^{5}$，$1 \leq r \leq \min(n, m)$，$1 \leq k \leq \min(n\cdot m, 10^{5})$）。

输出格式

输出一个实数，表示可以获得的最大期望捕获小鱼数量。

你的答案被认为是正确的，当且仅当其绝对误差或相对误差不超过 $10^{-9}$。即，设你的答案为 $a$，标准答案为 $b$，当且仅当

时，视为正确。

输入输出样例 #1

输入 #1

3 3 2 3

输出 #1

2.0000000000

输入输出样例 #2

输入 #2

12 17 9 40

输出 #2

32.8333333333

说明/提示

在第一个样例中，你可以把小鱼放在 $(2,1)$, $(2,2)$, $(2,3)$ 这三个格子中。这种情况下，四种渔网的可能放置方式（见下图绿色高亮区域）每次都能捕到两条小鱼，期望值也是 $2$。