Cod sursa(job #1230929)

Utilizator UCV_Buleandra_Teodorescu_BadeaUCV TEODORESCU BADEA CIUREZ UCV_Buleandra_Teodorescu_Badea Data 19 septembrie 2014 13:09:39
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.56 kb
#include <cstdio>
#include <cmath>

#define Nmax 50

using namespace std;

struct pt{
	int x;
	int y;
	pt() {
		x = 0;
		y = 0;
	}
} pos[Nmax];

int T, R, C, nr;
bool v[Nmax];
int main () {

	freopen("boundingbox.in", "r", stdin);
	freopen("boundingbox.out", "w", stdout);

	scanf("%d", &T);

	while(T--) {
		scanf("%d%d\n", &R, &C);

		char c;
		nr = 0;
		int sumaArie = 0;

		for(int i = 1; i <= R; ++i) {
			for(int j = 1; j <= C; ++j) {
				scanf("%c", &c);

				if(c == '1') {
					++nr;
					pos[nr].x = i;
					pos[nr].y = j;
				}

			}
			scanf("%c", &c);
		}

		int m = (1 << nr) - 1;
		for(int conf = 1; conf <= m; ++conf) {

			pt stangaSus, dreaptaJos;

			stangaSus.x = R + 1;
			stangaSus.y = C + 1;

			// Daca 1-ul current este ales
			int p = 1;
			for(int  i = 1; i <= nr; ++i) {
				if(conf & p) {
					if(pos[i].x < stangaSus.x)
						stangaSus.x = pos[i].x;
					if(pos[i].y < stangaSus.y)
						stangaSus.y = pos[i].y;

					if(pos[i].x > dreaptaJos.x)
						dreaptaJos.x = pos[i].x;
					if(pos[i].y > dreaptaJos.y)
						dreaptaJos.y = pos[i].y;
				}

				p = p << 1;
			}

			sumaArie += (dreaptaJos.x - stangaSus.x + 1) * (dreaptaJos.y - stangaSus.y + 1);
		}

		if(nr < R+C)
			m++;

		// Reduce fractia sumaArie/m

		int minim = sumaArie;
		if(m < minim)
			minim = m;

		int sqr = sqrt((double)minim);
		for(int i = 2; i <= sqr; ++i) {
			while(m % i == 0 && sumaArie % i == 0) {
				m /= i;
				sumaArie /= i;
			}
		}
		printf("%d/%d\n", sumaArie, m);
	}

	return 0;
}