Mai intai trebuie sa te autentifici.
Cod sursa(job #1230984)
Utilizator | Data | 19 septembrie 2014 13:50:15 | |
---|---|---|---|
Problema | Boundingbox | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Infoarena Cup 2014 | Marime | 1.64 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define nmax 55
#define ll long long
using namespace std;
int n, m, t, st[nmax];
char a[nmax][nmax];
vector <pair <int, int> > ones;
ll totalArea = 0LL, configs = 0LL, simp;
void solve() {
int left=0, right=0, up=0, down=0;
for(int i=0; i<int(ones.size()); i++) {
if(!st[i]) continue;
if(left == 0) left = ones[i].second;
else left = min(left, ones[i].second);
if(right == 0) right = ones[i].second;
else right = max(right, ones[i].second);
if(up == 0) up = ones[i].first;
else up = min(up, ones[i].first);
if(down == 0) down = ones[i].first;
else down = max(down, ones[i].first);
}
totalArea += (down-up+1) * (right-left+1);
configs++;
/*
cout<<"am luat unurile: ";
for(int i=0; i<int(ones.size()); i++) if(st[i]) cout<<i<<" "; cout<<"\n";
cout<<"left="<<left<<" | right="<<right<<" | up="<<up<<" | down="<<down<<"\n";
cout<<"imi acopera aria: "<<(down-up+1)*(right-left+1)<<"\n\n";
*/
}
void back(int k) {
for(int i=1; i>=0; i--) {
st[k] = i;
if(k == ones.size()-1) solve();
else back(k+1);
}
}
ll cmmdc(ll a, ll b) {
if(b == 0LL) return a;
return cmmdc(b, a%b);
}
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));
}
if(ones.size() == 0) totalArea = 1LL, configs = 1LL;
else back(0);
totalArea--;
simp = cmmdc(totalArea, configs);
g<<(totalArea/simp)<<"/"<<(configs/simp)<<"\n";
}
return 0;
}