## 题目大意
在 $n*m$ 的鱼缸里面，放入 $k$ 条鱼，再用一张 $r*r$的渔网再鱼缸里面捞鱼，看看平均每次能捞出多少条鱼，其实就是求一个 [期望值](https://baike.baidu.com/item/%E6%9C%9F%E6%9C%9B%E5%80%BC/8664642?fr=ge_ala)。
## 思路
1. 这道题我个人认为主体就是贪心，这个鱼放在什么位置最好呢？当然是最中间的位置，也就是 $(n+1)/x,(m+1)/2$ 这个位置。

2. 如果这个位置已经放了鱼呢，那么不妨我们可以看看他四周可不可以放下鱼。很显然可以用一个宽搜求出。

3. 如果这个位置像四周扩散总得有一个顺序吧，那必须是这个点被打捞出来的次数越多那么就越在前，这样我们就可以用优先队列来算，定义一个结构体，里面存储这个点还有它的被打捞的次数。

4. 我们又该如何算出这个点他被打捞出来的次数呢。首先我们应该会有一个暴力的做法，去枚举每一个网的左上角，看他能不能捞出来这条鱼。很显然是不行的，因为复杂度太高了。那么我们不妨用一个数学的公式来算这个点被打捞出来的次数 $(min(n,x+r-1)-max(x,r)+1)*(min(m,y+r-1)-max(r,y)+1)$ 我们为什么要用min或者max呢？主要是防止这个网的位置越界。

5. 大家想必都做过宽搜或者深搜吧，那是不是要用一个vis数组去记录他这个点是不是被访问过，这道题数据太大了，数组装不下，所以我们可以用一个set去记录

## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//个人习惯
ll n,m,r,k,xc,yc,ans;
struct node{
	ll x,y,gx;//位置和被打捞出来的次数
	bool operator<(node b) const{//判断优先级
	    return gx<b.gx;
	}
}; 
set<pair<ll,ll>> s;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
priority_queue<node> q;
ll f(ll x,ll y){//数学公式，用于计算当前点被打捞出来的次数
	return (min(n,x+r-1)-max(x,r)+1)*(min(m,y+r-1)-max(r,y)+1);
}
int main(){
	cin>>n>>m>>r>>k;
	xc=(n+1)/2;//中心点
	yc=(m+1)/2;
	q.push({xc,yc,f(xc,yc)});
	s.insert({xc,yc});
	while(k--){//注意：这里不是判空，而是看他有每有放完k条鱼
		ll x=q.top().x,y=q.top().y;
		ans+=q.top().gx;//计入答案
		q.pop();//删除
		for(int i=0;i<4;i++){
			ll nx=x+dx[i],ny=y+dy[i];//下一个点的坐标
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&s.count({nx,ny})==0){//判断它能不能进入队中
				s.insert({nx,ny});//标记
				q.push({nx,ny,f(nx,ny)});//进队
			}
		}
	}
	double hh=(n-r+1)*(m-r+1);//输出答案
	printf("%.10f",ans/hh);
	return 0;
}