萌新求助红黑树

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int inf = INT_MAX;

#define int long long
#define FOR(i,a,b) for(int i = a;i <= b;i++)
#define _FOR(i,a,b) for(int i = a;i >= b;i--)

template<typename T> void read(T &x)
{
    x = 0;int f = 1;
    char c = getchar();
    for(;!isdigit(c);c = getchar()) if(c == '-') f = -1;
    for(;isdigit(c);c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

struct node
{
	int x,y,num;
	bool operator < (const node &x) const 
	{
		return x.num > num;
	}
};

int mx[] = {0,1,-1,0,0};
int my[] = {0,0,0,1,-1};
priority_queue<node> q;
map<pair<int,int>,int> mp;
int n,m,r,k;
int calc(int x,int y) //有几个网能捞到它
{
	return (min(n,x + r - 1) - max(x,r) + 1) * (min(m,y + r - 1) - max(y,r) + 1);
} 

signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
	read(n),read(m),read(r),read(k);
	int x = (n + 1) >> 1,y = (m + 1) >> 1;
	q.push((node){x,y,calc(x,y)}); mp[make_pair(x,y)] = 1;
	double ans = 0;
	FOR(i,1,k) 
	{
		node tmp = q.top(); q.pop();
		x = tmp.x,y = tmp.y;
		ans += tmp.num;
		FOR(j,1,4) 
		{
			int nx = x + mx[i],ny = y + my[i];
			int qwq = mp[make_pair(nx,ny)];
			if(nx < 1 || nx > n || ny < 1 || ny > m || mp[make_pair(nx,ny)]) continue;
			q.push((node){nx,ny,calc(nx,ny)});
			mp[make_pair(nx,ny)] = 1;
		}
	}
	double tot = (n - r + 1) * (m - r + 1);
	printf("%.10f\n",ans / tot);
	return 0;	
}