Pagini recente » Cod sursa (job #2945264) | Cod sursa (job #1413375) | Cod sursa (job #2774928) | Cod sursa (job #2847048) | Cod sursa (job #1230929)
#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;
}