Cod sursa(job #1230903)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 19 septembrie 2014 12:56:52
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.3 kb
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <fstream>

using namespace std;


int main() {
  //probabil ceva 2 ^ n
  ifstream cin("boundingbox.in");
  ofstream cout("boundingbox.out");

  int T; cin >> T;
  for (; T--; ) {
    int R, C; cin >> R >> C;


    vector <string> M;
    for (int i = 0; i < R; ++i) {
      string s;cin >> s;
      M.push_back(s);
    }

    vector <pair <int, int> > go;

    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        if (M[i][j] == '1') {
          go.push_back(make_pair(i, j));
        }
      }
    }

    double answer = 0;
    for (int i = 1; i < (1 << go.size()); ++i) {

      int xmin = 100, ymin = 100;
      int xmax = 0, ymax = 0;

      for (int j = 0; j < go.size(); ++j) {
        if (i & (1 << j)) {
          xmin = min(go[j].first, xmin);
          xmax = max(go[j].first, xmax);

          ymin = min(go[j].second, ymin);
          ymax = max(go[j].second, ymax);

        }
      }
      cerr << xmin << " " << ymin << " " << xmax << " " << ymax << "\n";
      answer += (xmax - xmin + 1) * (ymax - ymin + 1);
    }
    int up = answer, down = (1 << go.size());
    cerr << up << " " << down << "\n";
    int x = __gcd(up, down);
    cout << up / x << "/" << down / x << "\n";
  }
  return 0;
}