Cod sursa(job #1230759)

Utilizator assa98Andrei Stanciu assa98 Data 19 septembrie 2014 11:12:40
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.53 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>

#define pe pair<int, int>
#define fi first
#define se second
#define mp make_pair

using namespace std;

ifstream fin("boundingbox.in");
ofstream fout("boundingbox.out");

const int MAX_N = 51;

string a[MAX_N];

long long A;
long long B;

long long cmmdc(long long a, long long b) {
    while(b) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

void solve(int n, int m) {
    vector<pe> v;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == '1') {
                v.push_back(mp(i,j));
            }
        }
    }

    B = ((long long) 1 << v.size());
    for(long long i = 1; i < B; i++) {
        int x1 = n, x2  = 0, y1 = m, y2 = 0;
        for(int j = 0; j < (int)v.size(); j++) {
            if(i & ((long long)1 << j)) {
                x1 = min(x1, v[j].fi);
                x2 = max(x2, v[j].fi);
                y1 = min(y1, v[j].se);
                y2 = max(y2, v[j].se);
            }
        }
        A += (x2 - x1 + 1) * (y2 - y1 + 1);
    }
}

int main() {
    int t;
    fin >> t;
    for(int k = 1; k <= t; k++) {
        A = 0;
        B = 0;
        
        int n, m;
        fin >> n >> m;
        for(int i = 0; i <= n; i++) {
            getline(fin, a[i]);
            //cout << a[i] << endl;
            a[i] = ' ' + a[i];
        }
        solve(n, m);
        long long d = cmmdc(A, B);
        fout << A/d << '/' << B/d << '\n';
    }
}