Cod sursa(job #1229621)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 17 septembrie 2014 20:19:55
Problema Boundingbox Scor Ascuns
Compilator cpp Status done
Runda Marime 2.1 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long int64;

const char IN_FILE[] = "boundingbox.in";
const char OUT_FILE[] = "boundingbox.out";
const int oo = 0x3f3f3f3f;

vector< pair<int, int> > Points;
pair<int64, int64> Answer;

inline int GetBit(const int mask, const int bit) {
    return (mask >> bit) & 1;
}

inline int64 GCD(int64 x, int64 y) {
    while (y) {
        int64 r = x % y;
        x = y;
        y = r;
    }
    return x;
}

inline int GetBoundingBoxArea(const vector< pair<int, int> > &points) {
    int minX = oo, maxX = -oo, minY = oo, maxY = -oo;
    for (const auto &p: points) {
        minX = min(minX, p.first);
        maxX = max(maxX, p.first);
        minY = min(minY, p.second);
        maxY = max(maxY, p.second);
    }
    if (minX > maxX || minY > maxY)
        return 0;
    return (maxX - minX + 1) * (maxY - minY + 1);
}

void Solve() {
    Answer = make_pair(0LL, 1LL << int(Points.size()));
    for (int mask = 0; mask < (1 << int(Points.size())); ++mask) {
        vector< pair<int, int> > points;
        for (int i = 0; i < int(Points.size()); ++i)
            if (GetBit(mask, i))
                points.push_back(Points[i]);
        Answer.first += GetBoundingBoxArea(points);
    }
    int64 d = GCD(Answer.first, Answer.second);
    Answer.first /= d;
    Answer.second /= d;
}

void Read(ifstream &cin) {
    Points = vector< pair<int, int> >();
    int rows, columns;
    cin >> rows >> columns;
    for (int x = 0; x < rows; ++x) {
        string row;
        cin >> row;
        for (int y = 0; y < columns; ++y)
            if (row[y] == '1')
                Points.push_back(make_pair(x, y));
    }
}

void Print(ofstream &cout) {
    cout << Answer.first << "/" << Answer.second << "\n";
}

int main() {
    ifstream cin("boundingbox.in");
    ofstream cout("boundingbox.out");
    int tests;
    cin >> tests;
    for (; tests > 0; --tests) {
        Read(cin);
        Solve();
        Print(cout);
    }
    cin.close();
    cout.close();
    return 0;
}