Pagini recente » Cod sursa (job #2232344) | Arhiva de probleme | Cod sursa (job #44015) | Cod sursa (job #2610294) | Cod sursa (job #1230888)
#include <fstream>
#include <algorithm>
#include <vector>
#define lint long long int
using namespace std;
inline lint gcd(lint a,lint b){
if(!b)
return a;
lint r=a%b;
while(r){
a=b;
b=r;
r=a%b;
}
return b;
}
/*class fractie{
lint a,b;
fractie() {a=0,b=1;}
fractie operator*=(fractie &x){
lint d=gcd(a,b);
a*=x.a;
b*=x.b;
a/=d;
b/=d;
return (*this);
}
};*/
vector<pair<int,int> > celule;
char mat[55][55];
inline int arie(int mask){
int lin_min=100;
int col_min=100;
int lin_max=0;
int col_max=0;
for(int i=0;i<celule.size();i++)
if(mask&(1<<i)){
lin_min=min(lin_min,celule[i].first);
col_min=min(col_min,celule[i].second);
lin_max=max(lin_max,celule[i].first);
col_max=max(col_max,celule[i].second);
}
int arie=(lin_max-lin_min+1)*(col_max-col_min+1);
if(lin_max-lin_min+1<0)
arie=0;
return arie;
}
int main()
{
ifstream cin("boundingbox.in");
ofstream cout("boundingbox.out");
ios_base::sync_with_stdio(false);
int t=0;
cin>>t;
int n=0,m=0;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mat[i][j];
celule.clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mat[i][j]=='1')
celule.push_back(make_pair(i,j));
lint ans=0;
for(int i=0;i<(1<<celule.size());i++)
ans+=arie(i);
lint a=ans;
lint b=(1ll<<celule.size());
lint d=gcd(a,b);
a/=d;
b/=d;
cout<<a<<'/'<<b<<'\n';
}
cin.close();
cout.close();
return 0;
}