Cod sursa(job #1230888)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 19 septembrie 2014 12:43:09
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.88 kb
#include <fstream>
#include <algorithm>
#include <vector>

#define lint long long int
using namespace std;

inline lint gcd(lint a,lint b){
    if(!b)
        return a;

    lint r=a%b;
    while(r){
        a=b;
        b=r;
        r=a%b;
    }

    return b;
}

/*class fractie{
    lint a,b;

    fractie() {a=0,b=1;}

    fractie operator*=(fractie &x){
        lint d=gcd(a,b);

        a*=x.a;
        b*=x.b;

        a/=d;
        b/=d;

        return (*this);
    }
};*/

vector<pair<int,int> > celule;

char mat[55][55];

inline int arie(int mask){
    int lin_min=100;
    int col_min=100;
    int lin_max=0;
    int col_max=0;

    for(int i=0;i<celule.size();i++)
        if(mask&(1<<i)){
            lin_min=min(lin_min,celule[i].first);
            col_min=min(col_min,celule[i].second);

            lin_max=max(lin_max,celule[i].first);
            col_max=max(col_max,celule[i].second);
        }

    int arie=(lin_max-lin_min+1)*(col_max-col_min+1);

    if(lin_max-lin_min+1<0)
        arie=0;

    return arie;
}

int main()
{
    ifstream cin("boundingbox.in");
    ofstream cout("boundingbox.out");

    ios_base::sync_with_stdio(false);

    int t=0;
    cin>>t;

    int n=0,m=0;
    while(t--){
        cin>>n>>m;

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>mat[i][j];

        celule.clear();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(mat[i][j]=='1')
                    celule.push_back(make_pair(i,j));

        lint ans=0;
        for(int i=0;i<(1<<celule.size());i++)
            ans+=arie(i);

        lint a=ans;
        lint b=(1ll<<celule.size());
        lint d=gcd(a,b);

        a/=d;
        b/=d;

        cout<<a<<'/'<<b<<'\n';
    }

    cin.close();
    cout.close();
    return 0;
}