Pagini recente » Cod sursa (job #1342093) | Cod sursa (job #3211668) | Cod sursa (job #68604) | Cod sursa (job #510019) | Cod sursa (job #541125)
Cod sursa(job #541125)
#include <cstdio>
#include <cmath>
#define nmax 310
#define eps 0.001
double st, dr, b[nmax][nmax], s[nmax][nmax], sol, v[nmax], q[nmax];
int a[nmax][nmax], n, m, r, c, p[nmax];
int verif(double x)
{
int i, j, st, dr, y, i1, i2;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++) b[i][j]=(double) a[i][j]-x;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
s[i][j]=s[i-1][j]+b[i][j];
for (i1=1; i1<=n; i1++)
for (i2=i1+r-1; i2<=n && i1+n/2>i2; i2++)
{
for (j=1; j<=m; j++) v[j]=v[j-1]+s[i2][j]-s[i1-1][j];
st=1;
dr=0;
if (v[c]>=0) return 1;
y=c+1;
for (j=1; y<=m; j++, y++)
{
while (v[j]<q[dr] && st<=dr) dr--;
while (p[st]+m/2<=y && st<=dr) st++;
dr++;
q[dr]=v[j];
p[dr]=j;
if (v[y]>=q[st]) return 1;
}
}
return 0;
}
int main()
{
freopen("balans.in","r",stdin);
freopen("balans.out","w",stdout);
scanf("%d %d %d %d",&n, &m, &r, &c);
int i, j;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++) scanf("%d",&a[i][j]);
double mij;
st=1<<30;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
{
a[i+n][j]=a[i][j+m]=a[i+n][j+m]=a[i][j];
if (a[i][j]<st) st=a[i][j];
if (a[i][j]>dr) dr=a[i][j];
}
n*=2;
m*=2;
while (fabs(st-dr)>eps)
{
mij=(st+dr)/2;
if (verif(mij))
{
st=mij;
sol=mij;
} else dr=mij;
}
printf("%.3lf\n",sol);
}