#include "quality.h"
void merge(int start, int end, int* arr, int* tmp) {
int i, j, k, mid = (start + end) / 2;
if(mid <= start) return;
merge(start, mid, arr, tmp);
merge(mid, end, arr, tmp);
for(i = start, j = mid, k = start; i < mid && j < end; k++) {
if(arr[i] < arr[j]) {
tmp[k] = arr[i];
i++;
}
else {
tmp[k] = arr[j];
j++;
}
}
for( ; i < mid; i++) {
tmp[k] = arr[i];
k++;
}
for( ; j < end; j++) {
tmp[k] = arr[j];
k++;
}
for(i = start; i < end; i++) {
arr[i] = tmp[i];
}
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int i, j, k, l, t = (H*W + 1)/2, m = 2000000024;
int tmp[9000012], arr[9000012], len = 0, c;
/*/*
for(k = 0; k < H; k++) {
for(l = 0; l < W; j++) {
arr[len] = Q[i][j];
len++;
}
}
merge(0, len, arr, tmp);
if(m > arr[t]) m = arr[t];
/**/
for(i = 0; i < R-H; i++) {
for(j = 0; j < C-W; j++) {
for(k = i; k < H+i; k++) {
for(l = j; l < W+j; l++) {
arr[len] = Q[i][j];
len++;
}
}
merge(0, len, arr, tmp);
if(m > arr[t]) m = arr[t];
len = 0;
}
}
return m;
}
