Cod sursa(job #1238297)

Utilizator MaarcellKurt Godel Maarcell Data 6 octombrie 2014 17:33:36
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#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;
}