1387.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

struct point{
	double x,y;
}p[201],tp;

double best;
int n,m,bn,bm,a[200][200],b[201],s[201],bx1,by1,bx2,by2,tx1,tx2,ty1,ty2;

double cross_product(point &a,point &b,point &c)
{
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

double solve_1d()
{
	double k,t;
	int i,top=0,left,right,mid,success;
	s[0]=0;
	for(i=1;i<=m;i++) s[i]=s[i-1]+b[i-1];
	k=0;
	for(i=m-bm;i>=0;i--){
		if (i==69){
			mid=i;
		}

		p[top].x=i+bm,p[top].y=s[i+bm],top++;
		tp.x=i,tp.y=s[i];
		while(top>=3&&cross_product(p[top-1],p[top-2],p[top-3])>-1e-10) p[top-2]=p[top-1],top--;

		left=0,right=top-1;
		for(;left<=right;){
			mid=(left+right)/2;
			if (mid==top-1||cross_product(tp,p[mid],p[mid+1])<-1e-10){
				success=mid;
				right=mid-1;
			}else{
				left=mid+1;
			}
		}

		t=(double)(p[success].y-s[i])/(p[success].x-i);
		if (t>k-1e-10){
			k=t;
			ty1=i,ty2=(int)(p[success].x-1+1e-10);
		}
	}
	return k;
}

void compute()
{
	int i,j,k;
	double t;
	best=-1;
	for(i=0;i<n;i++){
		tx1=i;

		memset(b,0,sizeof(b));
		for(j=i;j<n;j++){
			tx2=j;
			for(k=0;k<m;k++) b[k]+=a[j][k];
			if (j-i+1>=bn){
				
				if (i==76&&j==107){
					k=i+j;
				}
				
				t=solve_1d()/(j-i+1);
				if (t>best+1e-10){
					best=t;
					bx1=tx1,bx2=tx2,by1=ty1,by2=ty2;
				}
			}
		}
	}
}

int main()
{
//	freopen("test.in","r",stdin);

	int i,j;

	while(scanf("%d%d%d%d",&n,&m,&bn,&bm)==4){
		if (n==0) return 0;
		if (bn<=0) bn=1;
		if (bm<=0) bm=1;
		for(i=0;i<n;i++){
			for(j=0;j<m;j++)
				scanf("%d",&a[i][j]);
		}

		compute();

		printf("%d %d %d %d\n",bx1+1,by1+1,bx2+1,by2+1);
	}

	printf("*\n");

	return 0;
}