Pagini recente » Cod sursa (job #2986585) | Cod sursa (job #2058366) | Cod sursa (job #11150) | Cod sursa (job #1353288) | Cod sursa (job #1229621)
#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;
}