#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
#include <deque>
#include <iomanip>
using namespace std;
constexpr double epsilon = 1e-5;
void mk_partial_sums(const vector<vector<double> >& v,
vector<vector<double> >& rez){
const int n = v.size(), m = v.front().size();
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
rez[i][j] =
v[i-1][j-1] +
rez[i-1][j] +
rez[i][j-1] -
rez[i-1][j-1]; } } }
template <typename Cmp>
class min_deque{
deque<int> dq;
Cmp c;
public:
min_deque(const Cmp cc): c(cc){}
void push(const int x){
while(!dq.empty() && !c(dq.back(), x)){
dq.pop_back(); }
dq.push_back(x); }
int front(){
return dq.front(); }
void pop(const int x){
if(!dq.empty() && dq.front() == x){
dq.pop_front(); } } };
bool exista_subsecv_suma_pozitiva(const vector<double>& s_part, const int c, const int C){
auto cmp = [s_part](const int a, const int b){
return s_part[a] < s_part[b]; };
min_deque<decltype(cmp)> dq(cmp);
for(int i = c; i < s_part.size(); ++i){
dq.push(i-c);
if(s_part[i] - s_part[dq.front()] >= -epsilon){
return true; }
dq.pop(i-C); }
return false; }
bool exista_submat_suma_pozitiva(
const vector<vector<double> >& v, const int r, const int c, const int R, const int C){
const int n = v.size(), m = v.front().size();
static vector<vector<double> > sume_part(v.size()+1, vector<double>(v[0].size()+1, 0));
static vector<double> sume_part_linie(v[0].size()+1, 0);
mk_partial_sums(v, sume_part);
for(int i = 0; i < n; ++i){
for(int j = i+r; j <= i+R && j <= n; ++j){
transform(begin(sume_part[j]), end(sume_part[j]), begin(sume_part[i]),
begin(sume_part_linie), minus<double>());
if(exista_subsecv_suma_pozitiva(sume_part_linie, c, C)){
return true; } } }
return false; }
bool check(const vector<vector<int> >& mat, const double d, const int r, const int c, const int R, const int C){
static vector<vector<double> > m(mat.size(), vector<double>(mat[0].size(), 0));
for(int i = 0; i < mat.size(); ++i){
for(int j = 0; j < mat[i].size(); ++j){
m[i][j] = mat[i][j] - d; } }
return exista_submat_suma_pozitiva(m, r, c, R, C); }
double bin_search(const vector<vector<int> >& v, const int r, const int c, const int R, const int C){
double st, dr, mij;
for(st = 0, dr = 100000; st+epsilon < dr; ){
mij = st + (dr-st)/2;
if(check(v, mij, r, c, R, C)){
st = mij; }
else{
dr = mij; } }
return st; }
void citeste(vector<vector<int> >& v, int& r, int& c){
ifstream f("balans.in");
int n, m;
f >> n >> m >> r >> c;
v.resize(2*n, vector<int>(2*m));
for(int i = 0, di = n; i < n; ++i, ++di){
for(int j = 0, dj = m; j < m; ++j, ++dj){
f >> v[i][j];
v[i][dj] = v[di][j] = v[di][dj] = v[i][j]; } } }
int main(){
vector<vector<int> > v;
int r, c;
citeste(v, r, c);
ofstream g("balans.out");
g << fixed << setprecision(3) <<
bin_search(v, r, c, v.size()/2, v[0].size()/2);
return 0; }