Pagini recente » Cod sursa (job #898370) | Cod sursa (job #1413383) | Cod sursa (job #2414681) | Monitorul de evaluare | Cod sursa (job #1238297)
#include <iostream>
#include <fstream>
#include <string.h>
#define lld long long int
using namespace std;
int T,N,M,a[60][60],lin[60][60],col[60][60],cnt; char c;
lld gcd(lld a, lld b){
if (!b) return a;
return gcd(b,a%b);
}
int main(){
ifstream in("boundingbox.in");
ofstream out("boundingbox.out");
in >> T;
int k,i,j,u,w; lld cnt,area,x;
for (k=0; k<T; k++){
memset(lin,0,sizeof(lin));
memset(col,0,sizeof(col));
in >> N >> M;
for (i=1; i<=N; i++)
for (j=1; j<=M; j++){
in >> c;
a[i][j]=c-'0';
lin[i][j]=lin[i][j-1]+a[i][j];
col[j][i]=col[j][i-1]+a[i][j];
}
cnt=1; area=0;
for (i=1; i<=N; i++)
for (j=1; j<=M; j++)
for (u=i; u<=N; u++)
for (w=j; w<=M; w++)
if (lin[i][w]-lin[i][j-1]>0 && lin[u][w]-lin[u][j-1]>0 && col[j][u]-col[j][i-1]>0 && col[w][u]-col[w][i-1]>0){
cnt++;
area+=(u-i+1)*(w-j+1);
}
x=gcd(cnt,area);
out << area/x << "/" << cnt/x << "\n";
}
return 0;
}