Cod sursa(job #1230890)

Utilizator vladrochianVlad Rochian vladrochian Data 19 septembrie 2014 12:47:34
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.25 kb
#include <fstream>
#include <vector>
using namespace std;
typedef unsigned long long ui64;

int T, N, M, K;
char a[55][55];
ui64 conf, lim, A;
vector<pair<int, int> > unu;

ifstream fin("boundingbox.in");
ofstream fout("boundingbox.out");

inline void UpdMin(int &var, int val) {
	if (val < var)
		var = val;
}
inline void UpdMax(int &var, int val) {
	if (val > var)
		var = val;
}

ui64 Cmmdc(ui64 a, ui64 b) {
	if (!b)
		return a;
	return Cmmdc(b, a % b);
}

int main() {
	fin >> T;
	while (T--) {
		unu.clear();
		fin >> N >> M;
		for (int i = 0; i < N; ++i)
			fin >> a[i];
		for (int i = 0; i < N; ++i)
			for (int j = 0; j <= M; ++j)
				if (a[i][j] == '1')
					unu.push_back(make_pair(i, j));
		K = static_cast<int>(unu.size());
		lim = 1LL << K;
		A = 0;
		for (conf = 1; conf < lim; ++conf) {
			int xmin = 55, xmax = -1, ymin = 55, ymax = -1;
			for (int i = 0; i < K; ++i)
				if (conf & (1LL << i)) {
					UpdMin(xmin, unu[i].first);
					UpdMax(xmax, unu[i].first);
					UpdMin(ymin, unu[i].second);
					UpdMax(ymax, unu[i].second);
				}
			A += (xmax - xmin + 1) * (ymax - ymin + 1);
		}
		int cmmdc = Cmmdc(A, lim);
		A /= cmmdc;
		lim /= cmmdc;
		fout << A << "/" << lim << "\n";
	}
	return 0;
}