Cod sursa(job #1230794)

Utilizator Kira96Denis Mita Kira96 Data 19 septembrie 2014 11:37:43
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 3.18 kb
#include<fstream>
#define FOR(a,b,c) for(register int a=b;a<=c;++a)
#define ROF(a,b,c) for(register int a=b;a>=c;--a)
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<vector>
#define fi first
#define se second
#define FIT(a,b) for(vector<int>::iterator a=b.begin();a!=b.end();++a)
#include<ctime>
#include<cstring>
#include<bitset>
#include<cmath>
#include<iomanip>
#include<deque>
#define mod 1000000007
#define N 1000
#define SQ 1400
#define pb push_back
using namespace std;
ifstream f("boundingbox.in");
ofstream g("boundingbox.out");
long long gcd(long long a,long long b)
{
	if(!b)
		return a;
	return gcd(b,a%b);
}
long long freq[N],S,col[N][N],sum[N][N],lin[N][N],tot,kkt;
int n,m,T,i,j,k,l;
char s[N][N];
int main ()
{
	f>>T;
	while(T--)
	{
		f>>n>>m;
		for(i=1;i<=n;++i)
		f>>(s[i]+1);
		for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
		col[i][j]=lin[i][j]=sum[i][j]=0;
		
		for(i=1;i<=n*m;++i)
		freq[i]=0;
		
		for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
		{
			col[i][j]=col[i-1][j]+(s[i][j]=='1');
			lin[i][j]=lin[i][j-1]+(s[i][j]=='1');
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(s[i][j]=='1');
		}
		for(i=1;i<=n;++i)
		for(j=i;j<=n;++j)
		for(k=1;k<=m;++k)
		for(l=k;l<=m;++l)
		{
			if((col[j][k]-col[i-1][k])&&(col[j][l]-col[i-1][l])&&(lin[j][l]-lin[j][k-1])&&(lin[i][l]-lin[i][k-1]))
			{
				if(i==j&&k==l)
				{
					freq[1]++;
					continue;
				}
				if(i==j)
				{
					freq[l-k+1]+=(1LL<<(lin[j][l-1]-lin[j][k]));
					continue;
				}
				if(k==l)
				{
					freq[j-i+1]+=(1LL<<(col[j-1][k]-col[i][k]));
					continue;
				}
				int a11,a12,a21,a22;
				a11=a12=a21=a22=0;
				if(s[i][k]=='1')
					a11=1;
				if(s[i][l]=='1')
					a12=1;
				if(s[j][k]=='1')
					a21=1;
				if(s[j][l]=='1')
					a22=1;
				
				int plm=sum[j-1][l-1]-sum[i][l-1]-sum[j-1][k]+sum[i][k];
				int l_j=lin[j][l-1]-lin[j][k];
				int l_s=lin[i][l-1]-lin[i][k];
				int c_d=col[j-1][l]-col[i][l];
				int c_s=col[j-1][k]-col[i][k];
				
				long long lj=(1LL<<l_j);
				long long ls=(1LL<<l_s);
				long long cs=(1LL<<c_s);
				long long cd=(1LL<<c_d);
				long long cur=0;
				int area=(j-i+1)*(l-k+1);
				
				cur+=(lj-1)*(ls-1)*(cs-1)*(cd-1);
				if(a11)
					cur+=ls*cs*(lj-1)*(cd-1);
				if(a12)
					cur+=ls*cd*(lj-1)*(cs-1);
				if(a21)
					cur+=lj*cs*(ls-1)*(cd-1);
				if(a22)
					cur+=lj*cd*(cs-1)*(ls-1);
				if(a11&&a12)
					cur+=ls*cs*cd*(lj-1);
				if(a11&&a21)
					cur+=cs*lj*ls*(cd-1);
				if(a11&&a22)
					cur+=cs*cd*lj*ls;
				if(a12&&a21)
					cur+=cs*cd*lj*ls;
				if(a12&&a22)
					cur+=lj*ls*cd*(cs-1);
				if(a21&&a22)
					cur+=lj*cs*cd*(ls-1);
				if(a12&&a21&&a22)
					cur+=cs*cd*lj*ls;
				if(a11&&a21&&a22)
					cur+=cs*cd*lj*ls;
				if(a11&&a12&&a22)
					cur+=cs*cd*lj*ls;
				if(a11&&a12&&a21)
					cur+=cs*cd*lj*ls;
				if(a11&&a12&&a21&&a22)
					cur+=cs*cd*lj*ls;
				
				freq[area]+=cur*(1LL<<plm);
			}
		}
		tot=1;
		S=0;
		for(i=1;i<=n*m;++i)
		{
			tot+=freq[i];
			S+=freq[i]*i;
		}
		kkt=gcd(S,tot);
		g<<S/kkt<<"/"<<tot/kkt<<"\n";
	}
	return 0;
}

//Look at me! Look at me! The monster inside me has grown this big!