Pagini recente » Cod sursa (job #2557170) | Cod sursa (job #118089) | Cod sursa (job #1535131) | Cod sursa (job #1837160) | Cod sursa (job #1230906)
#include <iostream>
#include <fstream>
#include <vector>
#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;
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);
}
solve();
configs++;
simp = cmmdc(totalArea, configs);
g<<(totalArea/simp)<<"/"<<(configs/simp)<<"\n";
}
return 0;
}