Cod sursa(job #1230891)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 19 septembrie 2014 12:47:51
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.17 kb
#include <fstream>
using namespace std;
ifstream f("boundingbox.in");
ofstream g("boundingbox.out");
int v[5005],ind;
long long Result,number=1,R,C;
pair<int,int> Poz[100005];
void Read()
{
    int i;
    f>>R>>C;
    ind=0;
    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
        {
            char ch;
            f>>ch;
            if(ch=='1')
                Poz[++ind].first=i,Poz[ind].second=j;
        }
}

void Back(int level,int MaxL,int MinL,int MaxC,int MinC)
{
    Result+=(MaxL-MinL+1)*(MaxC-MinC+1);
    number++;
    if(MinC==0)
        MinC=100000;
    for(int i=v[level-1]+1;i<=ind;i++)
    {
        v[level]=i;
        Back(level+1,Poz[i].first,Poz[v[1]].first,max(MaxC,Poz[i].second),min(MinC,Poz[i].second));

    }
}
long long CMMDC(long long a,long long b)
{
    long long r=a%b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}
int main()
{
    int T;
    f>>T;
    while(T--)
    {
        Result=0;number=0;
        Read();
        Back(1,-1,0,-1,0);
        long long cmmdc=CMMDC(Result,number);
        g<<Result/cmmdc<<"/"<<number/cmmdc<<"\n";
    }
    return 0;
}