#include <bits/stdc++.h>
#include "locmin.h"

const int DI[] = {1, -1, 0, 0};
const int DJ[] = {0, 0, 1, -1};
long long mat[502][502];

static inline bool Verif(int i, int j, int n, int m) {
    for(int dir = 0; dir < 4; dir++) {
        int in = i + DI[dir];
        int jn = j + DJ[dir];
        if(1 <= in && in <= n && 1 <= jn && jn <= m) {
            if(mat[i][j] >= mat[in][jn]) return false;
        }
    }
    return true;
}

std::pair<int, int> find_locmin_point(int n, int m) {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            mat[i][j] = value(i, j);
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(Verif(i, j, n, m)) return {i, j};
        }
    }
}

/*std::pair<int, int> find_locmin_point(int n, int m) {
    int sus = 1, jos = n;
    int st = 1, dr = m;
    int mij;

    while(sus <= jos && st <= dr) {
        if(jos - sus >= dr - st) {
            mij = sus + (jos - sus) / 2;

            int mi = INT_MAX, col = -1;

            for(int val, c = st; c <= dr; c++) {
                val = value(mij, c);
                if(mi > val) {
                    mi = val;
                    col = c;
                }
            }

            bool okSus = (1 > mij - 1 || mi < value(mij - 1, col));
            bool okJos = (n < mij + 1 || mi < value(mij + 1, col));

            if(okSus && okJos) return {mij, col};
            else if(!okSus) jos = mij - 1;
            else            sus = mij + 1;
        }
        else {
            mij = st + (dr - st) / 2;

            int mi = INT_MAX, lin;
            for(int val, l = sus; l <= jos; l++) {
                val = value(l, mij);
                if(mi > val) {
                    mi = val;
                    lin = l;
                }
            }

            bool okSt = (1 > mij - 1 || mi < value(lin, mij - 1));
            bool okDr = (n < mij + 1 || mi < value(lin, mij + 1));
            if(okSt && okDr) return {lin, mij};
            else if(!okSt) dr = mij - 1;
            else           st = mij + 1;
        }
    }

    return {sus, st};
}*/
