Cod sursa(job #1230746)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 19 septembrie 2014 10:53:46
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.6 kb
#include <cstdio>

using namespace std;

struct coord
{
    int x, y;
}v[1005][55];

int n, m, t, aux, i, d, a, j, q, x, y, xmn, xmx, ymn, ymx;
long long cnt;
char s[55];

int div(int x, int y)
{
    if(x>y) return div(y, x);

    if(x==0) return y;
    return div(y%x, x);
}

int main()
{
    freopen("boundingbox.in", "r", stdin);
    freopen("boundingbox.out", "w", stdout);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        q=0;
        gets(s+1);
        for(i=1;i<=n;i++)
        {
            gets(s+1);
            for(j=1;j<=m;j++)
                if(s[j]=='1')
                {
                    v[t][++q].x=i;
                    v[t][q].y=j;
                }
        }
        y=1;
        x=0;

        if(q>18)
        {
            printf("\n");
            continue;
        }

        for(cnt=1;cnt<(1LL<<q);cnt++)
        {
            aux=cnt;
            xmn=51;
            ymn=51;
            xmx=-1;
            ymx=-1;
            i=0;
            while(aux)
            {
                i++;
                if(aux%2)
                {
                    if(v[t][i].x>xmx) xmx=v[t][i].x;
                    if(v[t][i].y>ymx) ymx=v[t][i].y;
                    if(v[t][i].x<xmn) xmn=v[t][i].x;
                    if(v[t][i].y<ymn) ymn=v[t][i].y;
                }
                aux/=2;
            }

            a=(xmx-xmn+1)*(ymx-ymn+1);
            x+=a;
            y++;
        }

        d=div(x, y);
        x/=d;
        y/=d;

        printf("%d/%d\n", x, y);
    }
    return 0;
}