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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>

using namespace std;

struct Dir {
    /** Długość boku */
    int k;
    /** Wartość X wektora */
    int x;
    /** Wartość Y wektora */
    int y;
    /** Kąt wektora */
    float angle;
public:
    Dir flip() {
        return Dir{ k, y, x, 90-angle };
    }
    Dir rot90() {
        return Dir{ k, y, -x, angle+90 };
    }
};

struct Rect {
    int x1, y1, x2, y2;

    Rect() : x1(0), y1(0), x2(0), y2(0) {}

    Rect(const Rect& src, int x, int y) {
        x1=min(src.x1, x); x2=max(src.x2, x);
        y1=min(src.y1, y); y2=max(src.y2, y);
    }

    inline int width() const { return x2-x1; }
    inline int height() const { return y2-y1; }
};


/**
 * Podstawowe możliwe wektory dla K z zadania (1..250) wraz z dodatykowymi informacjami
 */
Dir base[]={ { 1, 0, 1, 0 }, { 5, 3, 4, 36.8699 }, { 13, 5, 12, 22.6199 }, { 17, 8, 15, 28.0725 }, { 25, 7, 24, 16.2602 }, { 29, 20, 21, 43.6028 }, { 37, 12, 35, 18.9246 }, { 41, 9, 40, 12.6804 }, { 53, 28, 45, 31.8908 }, { 61, 11, 60, 10.3889 }, { 65, 16, 63, 14.25 }, { 65, 33, 56, 30.5102 }, { 73, 48, 55, 41.1121 }, { 85, 13, 84, 8.79741 }, { 85, 36, 77, 25.0576 }, { 89, 39, 80, 25.9892 }, { 97, 65, 72, 42.075 }, { 101, 20, 99, 11.4212 }, { 109, 60, 91, 33.3985 }, { 113, 15, 112, 7.62815 }, { 125, 44, 117, 20.6097 }, { 137, 88, 105, 39.9662 }, { 145, 17, 144, 6.73292 }, { 145, 24, 143, 9.52728 }, { 149, 51, 140, 20.016 }, { 157, 85, 132, 32.7791 }, { 169, 119, 120, 44.7603 }, { 173, 52, 165, 17.4923 }, { 181, 19, 180, 6.02558 }, { 185, 57, 176, 17.9453 }, { 185, 104, 153, 34.2055 }, { 193, 95, 168, 29.4871 }, { 197, 28, 195, 8.17123 }, { 205, 84, 187, 24.1895 }, { 205, 133, 156, 40.4497 }, { 221, 21, 220, 5.45262 }, { 221, 140, 171, 39.3076 }, { 229, 60, 221, 15.1893 }, { 233, 105, 208, 26.785 }, { 241, 120, 209, 29.8628 }, };

/** Możliwe kierunki do użycia zgodne z parametrami zadania */
vector<Dir> options;

/**
 * Obliczenie możliwych kierunków dla zadanego K
 */
void calcOptions(int k) {
    options.clear();
    for(auto d : base) {
        if(d.k>k) break;    // tylko do zadanego rozmiaru
        options.push_back(d);
        options.push_back(d.rot90());
        options.push_back(d.rot90().rot90());
        options.push_back(d.rot90().rot90().rot90());
        if(d.angle>0) {
            Dir f=d.flip();
            options.push_back(f);
            options.push_back(f.rot90());
            options.push_back(f.rot90().rot90());
            options.push_back(f.rot90().rot90().rot90());
        }
    }
    // sortujemy według konta, bo na tym będziemy działać głównie
    sort(options.begin(), options.end(), [](const Dir& a, const Dir& b) { return b.angle>a.angle; });
}

uint32_t res=0;
int width, height, k;

int startDir;

void calcRec(vector<Dir>& path, const Rect& size, int x, int y, int dir) {
    if( (size.width()>width || size.height()>=height) ) return;
    if(x<0) return;
    if(x==0 && y==0) {  // Koniec znaleziono wielokąt
        uint32_t widthSpace=width-size.width();
        uint32_t heightSpace=height-size.height();

        res+=widthSpace*heightSpace;
        return;
    }
    float angleLimit=options[dir].angle+180.0f;
    for(;;) {
        ++dir;
        if(dir==options.size()) {
            dir=0;
            angleLimit-=360.0f;
        }
        if(dir==0) break;
        const Dir& d=options[dir];
        if(d.angle>=angleLimit) break;
        const int nx=x+d.x, ny=y+d.y;
        Rect nsize(size, nx, ny);
        path.push_back(d);
        calcRec(path, nsize, nx, ny, dir);
        path.pop_back();
    }
}

uint32_t calc() {
    Rect zero;
    vector<Dir> path;

    for(int dir=0;dir<options.size();++dir) {
        const Dir& d=options[dir];
        startDir=dir;
        Rect r(zero, d.x, d.y);
        path.push_back(d);
        calcRec(path, r, d.x, d.y, dir);
        path.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>width>>height>>k;
    calcOptions(k);
    calc();
    cout<<res<<endl;

    return 0;
}