C++14(g++5.4) 解法, 执行用时: 330ms, 内存消耗: 63088K, 提交时间: 2018-10-06 15:13:22

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
const int MAXN = 1000 + 10;


int n, m, k;
int w[MAXN][MAXN];
int wx[MAXN][MAXN], wy[MAXN][MAXN];
long long valx[MAXN][MAXN], valy[MAXN][MAXN], totw[MAXN][MAXN];
typedef long long LL;
void solve(int a[MAXN][MAXN], LL ans[MAXN][MAXN]) {
  static LL sumv[MAXN << 1][MAXN], sumw[MAXN << 1][MAXN];
  const LL O = 1e3;
  
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      sumv[i + j][j] = sumv[i + j][j + 1] + a[i][j];
      sumw[i - j + O][j] = sumw[i - j + O][j - 1] + a[i][j];
    }
  }

  for (int i = k; i <= n; i++) {
    LL tot = 0;
    for (int j = 1; j <= k; j++) {
      tot += sumv[i + j][j] - sumv[i + j][k + 1];
    }
    for (int j = k + 1; j <= 2 * k - 1; j++) {
      tot += sumw[i - j + O][j] - sumw[i - j + O][k];
    }
    ans[i][k] = tot;

    for (int j = k + 1; j <= m - k + 1; j++) {
      tot -= sumv[i + (j - k)][j - k] - sumv[i + (j - k)][j];
      tot += sumw[i - (j + k - 1) + O][j + k - 1] - sumw[i - (j + k - 1) + O][j - 1];
      ans[i][j] = tot;
    }
  }
    
}
double sqr(double x) { return x * x; }
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d", &w[i][j]);
      wx[i][j] = w[i][j] * i;
      wy[i][j] = w[i][j] * j;
    }
  }

  solve(wx, valx);
  solve(wy, valy);
  solve(w, totw);

  double ans = 1e30;
  for (int i = k; i <= n; i++) {
    for (int j = k; j <= m - k + 1; j++) {
      double ansx = 1.0 * valx[i][j] / totw[i][j];
      double ansy = 1.0 * valy[i][j] / totw[i][j];
      //fprintf(stderr, "%.10f\n", sqr(ansx - (i - k + 1)) +
      //        sqr(ansy - j));
      
      ans = std::min(ans, sqr(ansx - (i - k + 1)) +
                     sqr(ansy - j));
    }
  }

  printf("%.10f\n", sqrt(ans));



}

C++11(clang++ 3.9) 解法, 执行用时: 237ms, 内存消耗: 98668K, 提交时间: 2018-10-06 14:00:16

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1010;
int a[N][N],n,m,k;
ll xa1[N][N],ya1[N][N],za1[N][N];//横行前缀和
ll xa2[N][N],ya2[N][N],za2[N][N];//左斜行前缀和
ll xa3[N][N],ya3[N][N],za3[N][N];//右斜行前缀和
ll ansx[N][N],ansy[N][N],ansz[N][N];
double ans=1e9,avex,avey;

int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d",&a[i][j]);
			xa1[i][j]=xa1[i][j-1]+i*a[i][j];
			ya1[i][j]=ya1[i][j-1]+j*a[i][j];
			za1[i][j]=za1[i][j-1]+a[i][j];

			xa2[i][j]=xa2[i-1][j+1]+i*a[i][j];
			ya2[i][j]=ya2[i-1][j+1]+j*a[i][j];
			za2[i][j]=za2[i-1][j+1]+a[i][j];

			xa3[i][j]=xa3[i-1][j-1]+i*a[i][j];
			ya3[i][j]=ya3[i-1][j-1]+j*a[i][j];
			za3[i][j]=za3[i-1][j-1]+a[i][j];
		}
	}
	for(int i=1; i+k-1<=n; i++){
		for(int ii=0; ii<k; ii++){
			ansx[i][k]+=xa1[i+ii][k+ii]-xa1[i+ii][k-ii-1];
			ansy[i][k]+=ya1[i+ii][k+ii]-ya1[i+ii][k-ii-1];
			ansz[i][k]+=za1[i+ii][k+ii]-za1[i+ii][k-ii-1];
		}
		for(int j=k+1; j+k-1<=m; j++){
			ansx[i][j]=ansx[i][j-1];
			ansy[i][j]=ansy[i][j-1];
			ansz[i][j]=ansz[i][j-1];

			ansx[i][j]-=xa2[i+k-1][j-k]-xa2[i-1][j];
			ansy[i][j]-=ya2[i+k-1][j-k]-ya2[i-1][j];
			ansz[i][j]-=za2[i+k-1][j-k]-za2[i-1][j];

			ansx[i][j]+=xa3[i+k-1][j+k-1]-xa3[i-1][j-1];
			ansy[i][j]+=ya3[i+k-1][j+k-1]-ya3[i-1][j-1];
			ansz[i][j]+=za3[i+k-1][j+k-1]-za3[i-1][j-1];
		}
		for(int j=k; j+k-1<=m; j++){
			//cout<<i<<" "<<j<<" :"<<ansx[i][j]<<" "<<ansy[i][j]<<" "<<ansz[i][j]<<endl;
			avex=1.0*ansx[i][j]/(1.0*ansz[i][j])-1.0*i;
			avey=1.0*ansy[i][j]/(1.0*ansz[i][j])-1.0*j;
			//printf("%.10lf %.10lf\n",avex,avey);
			ans=min(ans,avex*avex+avey*avey);
		}
	}
	printf("%.10lf\n",pow(ans,0.5));
	return 0;
}