Cod sursa(job #1231083)

Utilizator SmarandaMaria Pandele Smaranda Data 19 septembrie 2014 14:58:58
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 2.08 kb
#include <cstdio>

using namespace std;

struct Point {
    int x, y;
};

int a [55][55], u;
Point P [55];
char s [1001];
Point P1 [55];

int minimx () {
   int g = 200000, i;
    for (i = 1; i <= u; i ++)
        if (P1 [i].x < g)
            g = P1 [i].x;
    return g;
}

int minimy () {
   int g = 200000, i;
    for (i = 1; i <= u; i ++)
        if (P1 [i].y < g)
            g = P1 [i].y;
    return g;
}

int maximx () {
   int g = -1, i;
    for (i = 1; i <= u; i ++)
        if (P1 [i].x > g)
            g = P1 [i].x;
    return g;
}

int maximy () {
   int g = -1, i;
    for (i = 1; i <= u; i ++)
        if (P1 [i].y > g)
            g = P1 [i].y;
    return g;
}

int gcd (long long x , long long y) {
    long long r;
    while (y) {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main () {
    int n, m, i, j, ns = 0, b, v, c, l, h, T, t;
    long long aria = 0, cm;
    freopen ("boundingbox.in", "r", stdin);
    freopen ("boundingbox.out", "w", stdout);

    scanf ("%d", &T);
    for (t = 1; t <= T; t ++) {
        u = aria = ns = cm = 0;
        scanf ("%d%d\n", &n, &m);

        for (i = 1; i <= n; i ++) {
            gets (s + 1);
            for (j = 1; j <= m; j ++) {
                a  [i][j] = s [j] - '0';
                if (a [i][j] == 1) {
                    ns ++;
                    P [++ u].x = i;
                    P [u].y = j;
                }
            }
        }
        c = ns;
        ns = (1 << ns);
        for (v = 1; v < ns; v ++) {
            u = 0;
            for (b = 0; b < c; b ++)
                if (v & (1 << b)) {
                    P1 [++ u] = P [b + 1];
                }
            l = maximx () - minimx () + 1;
            h = maximy () - minimy () + 1;
            aria = (long long)aria + l * h;
        }
        c = ns;
       cm = gcd (aria, c);
       if (cm) {
       aria = aria / cm;
       c = c / cm;

       }
        printf ("%lld", aria);
        printf ("/");
        printf ("%d\n", c);
    }
    return 0;
}