Cod sursa(job #1713700)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 6 iunie 2016 10:51:29
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.65 kb
#include <cstdio>
#define MAXN 50
int s[MAXN+1][MAXN+1], lin[MAXN+1][MAXN+1], col[MAXN+1][MAXN+1];
bool m[MAXN+1][MAXN+1];
inline int dreptunghi(int l1, int c1, int l2, int c2){
    return s[l2][c2]-s[l2][c1-1]-s[l1-1][c2]+s[l1-1][c1-1];
}
inline int linie(int l, int c1, int c2){
    return lin[l][c2]-lin[l][c1-1];
}
inline int coloana(int c, int l1, int l2){
    return col[l2][c]-col[l1-1][c];
}
int main(){
    int a, b, c, d, e, nrlin, nrcol, teste, i, j, l1, c1, l2, c2, p;
    unsigned long long sum, ans, rez, nrsol;
    bool x, y, z, t;
    char ch;
    FILE *fin, *fout;
    fin=fopen("boundingbox.in", "r");
    fout=fopen("boundingbox.out", "w");
    fscanf(fin, "%d", &teste);
    for(; teste; teste--){
        fscanf(fin, "%d%d ", &nrlin, &nrcol);
        for(i=1; i<=nrlin; i++){
            for(j=1; j<=nrcol; j++){
                ch=fgetc(fin);
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
                lin[i][j]=lin[i][j-1];
                col[i][j]=col[i-1][j];
                if(ch=='1'){
                    s[i][j]++;
                    lin[i][j]++;
                    col[i][j]++;
                    m[i][j]=1;
                }else{
                    m[i][j]=0;
                }

            }
            fgetc(fin);
        }
        ans=0;
        for(l1=1; l1<=nrlin; l1++){
            for(c1=1; c1<=nrcol; c1++){
                for(l2=l1+1; l2<=nrlin; l2++){
                    for(c2=c1+1; c2<=nrcol; c2++){
                        if((l1+1<l2)&&(c1+1<c2)) e=dreptunghi(l1+1, c1+1, l2-1, c2-1);
                        else e=0;
                        a=linie(l1, c1+1, c2-1);
                        b=linie(l2, c1+1, c2-1);
                        c=coloana(c1, l1+1, l2-1);
                        d=coloana(c2, l1+1, l2-1);
                        x=m[l1][c1];
                        y=m[l1][c2];
                        z=m[l2][c1];
                        t=m[l2][c2];
                        sum=0;
                        for(p=0; p<16; p++){
                            if(((!(p&1))||(x))&&((!(p&2))||(y))&&((!(p&4))||(z))&&((!(p&8))||(t))){
                                nrsol=1LL<<e;
                                if((p&1)||(p&2)) nrsol<<=a;
                                else nrsol*=(1LL<<a)-1;
                                if((p&1)||(p&4)) nrsol<<=c;
                                else nrsol*=(1LL<<c)-1;
                                if((p&2)||(p&8)) nrsol<<=d;
                                else nrsol*=(1LL<<d)-1;
                                if((p&4)||(p&8)) nrsol<<=b;
                                else nrsol*=(1LL<<b)-1;
                                sum+=nrsol;
                            }
                        }
                        ans+=sum*(l2-l1+1)*(c2-c1+1);
                    }
                }
            }
        }
        for(i=1; i<=nrlin; i++){
            for(c1=1; c1<=nrcol; c1++){
                for(c2=c1+1; c2<=nrcol; c2++){
                    if((m[i][c1])&&(m[i][c2])) ans+=(1LL<<linie(i, c1+1, c2-1))*(c2-c1+1);
                }
            }
        }
        for(j=1; j<=nrcol; j++){
            for(l1=1; l1<=nrlin; l1++){
                for(l2=l1+1; l2<=nrlin; l2++){
                    if((m[l1][j])&&(m[l2][j])) ans+=(1LL<<coloana(j, l1+1, l2-1))*(l2-l1+1);
                }
            }
        }
        ans+=dreptunghi(1, 1, nrlin, nrcol);
        rez=1LL<<dreptunghi(1, 1, nrlin, nrcol);
        while((ans>0)&&(ans%2==0)){
            ans>>=1;
            rez>>=1;
        }
        fprintf(fout, "%llu/%llu\n", ans, rez);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}