Cod sursa(job #1230930)

Utilizator visanrVisan Radu visanr Data 19 septembrie 2014 13:09:58
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.41 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int NMAX = 55;

int T, N, M, X[NMAX], Y[NMAX], K;
char S[NMAX][NMAX];
long long Ans;

long long GCD(long long A, long long B)
{
    if(!B) return A;
    return GCD(B, A % B);
}

int main()
{
    freopen("boundingbox.in", "r", stdin);
    freopen("boundingbox.out", "w", stdout);

    scanf("%i", &T);
    for(; T; T --)
    {
        Ans = 0;
        K = 0;

        scanf("%i %i\n", &N, &M);
        for(int i = 1; i <= N; ++ i)
        {
            gets(S[i] + 1);
            for(int j = 1; j <= M; ++ j)
                if(S[i][j] == '1')
                    X[K] = i, Y[K ++] = j;
        }

        for(int Conf = 1; Conf < (1 << K); ++ Conf)
        {
            int MinX = N + 1, MaxX = 0, MinY = M + 1, MaxY = 0;
            for(int i = 0; i < K; ++ i)
                if(Conf & (1 << i))
                {
                    MinX = min(MinX, X[i]);
                    MaxX = max(MaxX, X[i]);
                    MinY = min(MinY, Y[i]);
                    MaxY = max(MaxY, Y[i]);
                }

            Ans += 1LL * (MaxX - MinX + 1) * (MaxY - MinY + 1);
        }

        long long Up = Ans, Down = (1LL << K), NowGCD = GCD(Up, Down);
        Up /= NowGCD;
        Down /= NowGCD;

        printf("%lld/", Up);
        printf("%lld\n", Down);
    }
}