1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include <vector>
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <string>
 
int count_inscribed_rectangles(size_t m, size_t n) {
    // Formula romelic gvazlevs kvela shesazlo "qve" martkutxedis raodenobas M|N martkutxedshi.
    return m*n*(m+1)*(n+1)/4-1;
}
 
void generate_m(std::string const& input, std::string const& output) {
    using std::string;
    using std::ifstream;
    using std::ofstream;
    using std::vector;
    ifstream read(input.c_str(),std::ios::in);
    ofstream write(output.c_str(),std::ios::out);
    if (!read || !write) {
        std::cerr << "IO failed." << std::endl;
    }
    int num_of_rects = 0;
    int sum_of_inscribed_rects = 0;
    vector<std::string> items;
    string line;
    // Pirveli xazi romelic sheicavs ra kvadratis zomas ar gvchirdeba, cavikitxot da gadavagdot.
    if (!std::getline(read,line)) {
        std::cerr << "Error" << std::endl;
        exit(EXIT_FAILURE);
    }
    string::size_type prev;
    string::size_type start_idx;
    string::size_type end_idx;
    prev = start_idx = end_idx = 0;
    // Cavikitxot koveli xazi vectorshi.
    while (std::getline(read,line)) {
        items.push_back(line);
    }
    typedef std::vector<std::string>::const_iterator const_iter;
    // Koveli xazisatvis:
    for (const_iter i = items.begin(); i != items.end(); ++i) {
         // Vcadot rom vipovot "1"
         while ((start_idx = i->find('1',prev)) != string::npos) {
             end_idx = i->find('0',start_idx+1);
             end_idx = (end_idx==string::npos) ? line.size() : end_idx;
             prev = end_idx + 1;
             --end_idx;
             // Shevamocmot tu napovni martkudxedi ukve ganvixilet
             if (i != items.begin() && (i-1)->operator[](start_idx)== '1' && (i-1)->operator[](end_idx) == '1') {
                 if (start_idx>0&&end_idx<line.size()-1) {
                     if ((i-1)->operator[](start_idx-1)=='0'&&(i-1)->operator[](end_idx+1)=='0') continue;
                 } else if (start_idx > 0) {
                     if ((i-1)->operator[](start_idx-1) == '0') continue;
                 } else if (end_idx<line.size()-1) {
                     if ((i-1)->operator[](end_idx+1)=='0') continue;
                 }
             }
             int n = end_idx - start_idx + 1;
             int m = 1;
             const_iter j = i;
             // Davadginot napovni martkudxedis m zoma:
             while (++j != items.end()) {
                 if (j->operator[](start_idx) == '0' || j->operator[](end_idx) == '0') break;
                 if (start_idx > 0 && end_idx < line.size() - 1) {
                     if (j->operator[](start_idx - 1) != '0' || (i-1)->operator[](end_idx + 1) != '0') break;
                 } else if (start_idx > 0) {
                     if (j->operator[](start_idx - 1) != '0') break;
                 } else if (end_idx < line.size() - 1) {
                     if (j->operator[](end_idx + 1 ) != '0') break;
                 }
                 ++m;
             }
             sum_of_inscribed_rects += count_inscribed_rectangles(m,n);
             ++num_of_rects;
             // Continue
         }
         prev = 0;
    }
    write << "A: " << num_of_rects << "\tB: " << sum_of_inscribed_rects << std::endl;
}