CF912D 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$，当且仅当 $$ \frac{|a-b|}{\max(1, |b|)} \leq 10^{-9} $$ 时，视为正确。

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