Nu aveti permisiuni pentru a descarca fisierul grader_test18.ok
Cod sursa(job #1230744)
Utilizator | Data | 19 septembrie 2014 10:51:46 | |
---|---|---|---|
Problema | Boundingbox | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Infoarena Cup 2014 | Marime | 1.69 kb |
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
const int INFINITE = 100;
inline int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int sum;
void backt(vector< pair<int, int> > &elements, int pos, int x1, int y1, int x2, int y2) {
if (static_cast<int>(elements.size()) == pos) {
if (x1 != INFINITE && y1 != INFINITE) {
sum += (x2 - x1 + 1) * (y2 - y1 + 1);
}
} else {
backt(elements, pos + 1, x1, y1, x2, y2);
backt(elements, pos + 1, min(x1, elements[pos].first),
min(y1, elements[pos].second),
max(x2, elements[pos].first),
max(y2, elements[pos].second));
}
}
int main() {
ifstream fin("boundingbox.in");
ofstream fout("boundingbox.out");
int tests; vector< pair<int, int> > elements;
for (fin >> tests; tests; -- tests) {
int n, m;
fin >> n >> m;
elements.clear();
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
char ch;
fin >> ch;
while (ch == ' ' || ch == '\n') {
fin >> ch;
}
if (ch == '1') {
elements.push_back(make_pair(i, j));
}
}
}
if (static_cast<int>(elements.size()) <= 12) {
sum = 0;
backt(elements, 0, INFINITE, INFINITE, 0, 0);
fout << sum / gcd(sum, 1 << elements.size()) << "/" << (1 << elements.size()) / gcd(sum, (1 << elements.size())) << "\n";
}
}
return 0;
}