Cod sursa(job #1230922)

Utilizator harababurelPuscas Sergiu harababurel Data 19 septembrie 2014 13:04:59
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 55
#define ll long long
using namespace std;

int t, n, m, imin, imax, jmin, jmax, s[nmax][nmax], area, onesInside;
char a[nmax][nmax];
vector <pair <int, int> > ones;
ll totalArea, configs, simp;

ll cmmdc(ll a, ll b) {
	if(b == 0LL) return a;
	return cmmdc(b, a%b);
}

int maximum(int a, int b, int c) { return max(max(a, b), c); }
int minimum(int a, int b, int c) { return min(min(a, b), c); }

void solve() {
	for(int a=0; a<ones.size(); a++)
		for(int b=a; b<ones.size(); b++)
			for(int c=b; c<ones.size(); c++) {
				if(b==c && a!=b) continue; //1 1 3 si 1 3 3 is identice
				//fa ceva
				imin = minimum(ones[a].first, ones[b].first, ones[c].first);
				imax = maximum(ones[a].first, ones[b].first, ones[c].first);
				jmin = minimum(ones[a].second, ones[b].second, ones[c].second);
				jmax = maximum(ones[a].second, ones[b].second, ones[c].second);

				area = (imax-imin+1) * (jmax-jmin+1);
				onesInside = s[imax][jmax] - s[imax][jmin-1] - s[imin-1][jmax] + s[imin-1][jmin-1];
				if(a == b && b == c) onesInside -= 1;
				else if(a==b || b==c) onesInside -= 2;
				else onesInside -= 3;

				//cout<<"am fixat colturile la "<<a+1<<", "<<b+1<<", "<<c+1<<" si am obtionut aria = "<<area<<"\n";

				//am 2^onesInside configuratii, toate imi dau aria curenta
				totalArea += (1LL<<onesInside) * area;
				configs += (1LL<<onesInside);
			}
}

int main() {
	ifstream f("boundingbox.in");
	ofstream g("boundingbox.out");

	f>>t;
	while(t--) {
		ones.clear();
		totalArea = 0LL;
		configs = 0LL;
		for(int i=0; i<nmax; i++)
			for(int j=0; j<nmax; j++) s[i][j] = 0;

		f>>n>>m;
		for(int i=1; i<=n; i++) 
			for(int j=1; j<=m; j++) {
				f>>a[i][j];
				if(a[i][j] == '1') ones.push_back(make_pair(i, j));

				s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + (a[i][j]=='1'? 1:0);
			}

		sort(ones.begin(), ones.end());


		solve();
		configs++;
		simp = cmmdc(totalArea, configs);
		g<<(totalArea/simp)<<"/"<<(configs/simp)<<"\n";
	}

	return 0;
}