Cod sursa(job #1230785)

Utilizator S7012MYPetru Trimbitas S7012MY Data 19 septembrie 2014 11:26:50
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#define x first
#define y second
#define MLT (1<<30)
using namespace std;

typedef pair<int,int> per;

int t,n,m,sum;

int cmmdc(int a,int b) {
    for(int c;b;c=a%b,a=b,b=c);
    return a;
}

int main()
{
    ifstream f("boundingbox.in");
    ofstream g("boundingbox.out");
    for(f>>t;t--;) {
        f>>n>>m;
        vector<per> ones; sum=0;
        for(int i=0; i<n; ++i) {
            string s; f>>s;
            for(int j=0; j<m; ++j) if(s[j]=='1') ones.push_back(make_pair(i,j));
        }
        int l=(1<<ones.size());
        for(int s=1; s<l; ++s) {
            int xmi=MLT,xma=-MLT,ymi=MLT,yma=-MLT;
            for(int i=0; i<ones.size(); ++i) if(s&(1<<i)) {
                xmi=min(xmi,ones[i].x); xma=max(xma,ones[i].x);
                ymi=min(ymi,ones[i].y); yma=max(yma,ones[i].y);
            }
            //cerr<<xmi<<' '<<xma<<' '<<ymi<<' '<<yma<<'\n';
            sum+=(xma-xmi+1)*(yma-ymi+1);
        }
        int cm=cmmdc(sum,l);
        g<<sum/cm<<'/'<<l/cm<<'\n';
    }
    return 0;
}