Cod sursa(job #1230829)

Utilizator till.lindemannTill Lindemann till.lindemann Data 19 septembrie 2014 12:02:26
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.33 kb
#include <fstream>
#define DIM 55
#define infile "boundingbox.in"
#define outfile "boundingbox.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

int A[DIM][DIM], L[DIM][DIM], C[DIM][DIM];

char ch;

int t, m, n;

int main () {
    f >> t;
    long long X = 0, Y = 1;
    while(t--) {
        f >> m >> n;
        X = 0; Y = 1;
        for (int i=1; i<=m; ++i) {
            for (int j=1; j<=n; ++j) {
                f >> ch;
                A[i][j] = ch-'0';
                L[i][j] = C[i][j] = A[i][j];
                L[i][j] += L[i][j-1];
                C[i][j] += C[i-1][j];
            }
        }
        for (int i=1; i<=m; ++i)
            for (int j=1; j<=n; ++j)
                for (int ii=i; ii<=m; ++ii)
                    for (int jj=j; jj<=n; ++jj) {
                        if (L[i][jj] - L[i][j-1] > 0 && L[ii][jj] - L[ii][j-1] > 0) {
                            if(C[ii][j] - C[i-1][j] > 0 && C[ii][jj] - C[i-1][jj] > 0)
                                Y++, X += 1LL*(ii-i+1)*(jj-j+1);
                        }
                    }
            long long XX=X, YY=Y;
        while(YY!=0) {
            long long r = XX%YY;
            XX = YY;
            YY = r;
        }
        X /= XX;
        Y /= XX;
        g << X <<"/" << Y << "\n";
    }

    return 0;
}