Cod sursa(job #1288747)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 9 decembrie 2014 00:58:59
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.66 kb
#include<iostream>
#include<fstream>
#include<string.h>
#include<algorithm>
using namespace std;

#define NMAX 52

int s[NMAX][NMAX],a[NMAX][NMAX],lin[NMAX],col[NMAX];
long long p[NMAX],P[NMAX];
char sir[NMAX];

long long gcd(long long a, long long b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}

int sum(int i, int j, int k, int l)
{
	if(k<i || l<j)
		return 0;
	return s[k][l]-s[k][j-1]-s[i-1][l]+s[i-1][j-1];
}

void solve(long long &x, long long &y, int n, int m)
{
	int i,j,k,l,sus,jos,st,dr,inside,arie;
	long long d;
	x=0;
	y=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			for(k=i;k<=n;k++)
				for(l=j;l<=m;l++) {
					sus=sum(i,j+1,i,l-1);
					jos=sum(k,j+1,k,l-1);
					st=sum(i+1,j,k-1,j);
					dr=sum(i+1,l,k-1,l);
					inside=sum(i+1,j+1,k-1,l-1);
					arie=(k-i+1)*(l-j+1);
					if(i==k && j==l) {
						if(a[i][j])
							y=0LL+y+1;
						continue;
					}
					if(i==k) {
						if(a[i][j] && a[i][l])
							y=0LL+y+1LL*p[sus]*arie;
						continue;
					}
					else if(j==l) {
						if(a[i][j] && a[k][j])
							y=0LL+y+1LL*p[st]*arie;
						continue;
					}
					
					y=0LL+y+1LL*P[sus]*P[jos]*P[st]*P[dr]*p[inside]*arie;
					if(a[i][j]) 
						y=0LL+y+1LL*P[jos]*P[dr]*p[inside+sus+st]*arie;
					if(a[k][l])
						y=0LL+y+1LL*P[sus]*P[st]*p[inside+jos+dr]*arie;
					if(a[i][l])
						y=0LL+y+1LL*P[jos]*P[st]*p[inside+sus+dr]*arie;
					if(a[k][j])
						y=0LL+y+1LL*P[sus]*P[dr]*p[inside+jos+st]*arie;
					if(a[i][j] && a[k][j])
						y=0LL+y+1LL*P[dr]*p[inside+st+sus+jos]*arie;
					if(a[i][l] && a[k][l])
						y=0LL+y+1LL*P[st]*p[inside+dr+sus+jos]*arie;
					if(a[i][j] && a[i][l])
						y=0LL+y+1LL*P[jos]*p[inside+st+dr+sus]*arie;
					if(a[k][j] && a[k][l])
						y=0LL+y+1LL*P[sus]*p[inside+st+dr+jos]*arie;
					
					if(a[i][j] && a[k][l])
						y=0LL+y+1LL*p[inside+st+dr+sus+jos]*arie;
					if(a[k][j] && a[i][l])
						y=0LL+y+1LL*p[inside+st+dr+sus+jos]*arie;
					if(a[i][j] && a[i][l]) {
						if(a[k][l])
							y=0LL+y+1LL*p[inside+sus+jos+st+dr]*arie;
						if(a[k][j])
							y=0LL+y+1LL*p[inside+sus+jos+st+dr]*arie;
					}
					if(a[k][j] && a[k][l]) {
						if(a[i][j])
							y=0LL+y+1LL*p[inside+sus+jos+st+dr]*arie;
						if(a[i][l])
							y=0LL+y+1LL*p[inside+sus+jos+st+dr]*arie;
					}
					if(a[i][j] && a[i][l] && a[k][j] && a[k][l])
						y=0LL+y+1LL*p[inside+sus+jos+st+dr]*arie;
				}
	x=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i][j])
				x++;
	x=p[x];
	d=gcd(x,y);
	if(d) {
		x=1LL*x/d;
		y=1LL*y/d;
	}
}

void brute(long long &y, long long &x, int n, int m)
{
	int nr,i,j,maxx,maxy,minx,miny;
	long long d;
	nr=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(a[i][j]) {
				lin[++nr]=i;
				col[nr]=j;
			}
	x=0;
	y=p[nr];
	for(i=1;i<=y-1;i++) {
		maxx=maxy=0;
		minx=miny=(1<<30);
		for(j=0;j<=nr-1;j++)
			if(i & (1<<j)) {
				maxx=max(maxx,lin[j+1]);
				maxy=max(maxy,col[j+1]);
				minx=min(minx,lin[j+1]);
				miny=min(miny,col[j+1]);
			}
		x=0LL+x+(maxx-minx+1)*(maxy-miny+1);
	}
	d=gcd(x,y);
	if(d) {
		x=1LL*x/d;
		y=1LL*y/d;
	}
}
	
int main ()
{
	int t,i,n,m,j;
	long long x,y;
	ifstream f("boundingbox.in");
	ofstream g("boundingbox.out");
	f>>t;
	p[0]=1;
	for(i=1;i<=50;i++)
		p[i]=1LL*p[i-1]*2;
	for(i=1;i<=50;i++)
		P[i]=(1LL<<i)-1;
	while(t--) {
		f>>n>>m;
		for(i=1;i<=n;i++) {
			f>>(sir+1);
			for(j=1;j<=m;j++)
				if(sir[j]=='1')
					a[i][j]=1;
				else a[i][j]=0;
		}
		solve(x,y,n,m);
		g<<y<<"/"<<x<<'\n';
		//brute(x,y,n,m);
		//g<<y<<"/"<<x<<'\n';
	}
	f.close();
	g.close();
	return 0;
}