#include "locmin.h"
#include <bits/stdc++.h>
const int MAXN = 500;

long long mat[MAXN + 2][MAXN + 2];
int dl[] = { 0, -1, 1, 0 };
int dc[] = { 1, 0, 0, -1 };

bool verif( int i, int j ) {
    int cnt = 0;
    for( int dir = 0; dir < 4; dir++ )
        if( mat[i + dl[dir]][j + dc[dir]] >= mat[i][j] )
            cnt++;
    return cnt == 4;
}

std::pair <int, int> find_locmin_point(int N, int M) {
    int i, j, n, m;
    n = N;
    m = M;
    if( n == 1 && m == 1 )
        return { 1, 1 };

    for( i = 1; i <= n; i++ )
        mat[i][0] = mat[i][m + 1] = LLONG_MAX;

    for( j = 1; j <= m; j++ )
        mat[0][j] = mat[n + 1][j] = LLONG_MAX;

    for( j = 1; j <= n; j++ )
        mat[1][j] = -1;

    i = 1;
    int cnt, mij;
    mij = m / 2;
    if( m % 2 == 1 ) {
        // - - - - -
        j = mij + 1;
        mat[i][j] = value( i, j );
        for( cnt = 1; cnt <= mij; cnt++ ) {
            mat[i][j + cnt] = value( i, j + cnt );
            mat[i][j - cnt] = value( i, j - cnt );
            if( verif( i, j + cnt - 1 ) )
                return { i, j + cnt - 1 };
            if( verif( i, j - cnt + 1 ) )
                return { i, j - cnt + 1 };
        }
    } else {
        // - - - -
        j = mij;
        mat[i][j] = value( i, j );
        for( cnt = 1; cnt < mij; cnt++ ) {
            mat[i][j + cnt] = value( i, j + cnt );
            mat[i][j - cnt] = value( i, j - cnt );
            if( verif( i, j + cnt - 1 ) )
                return { i, j + cnt - 1 };
            if( verif( i, j - cnt + 1 ) )
                return { i, j - cnt + 1 };
        }
    }
    return { 1, m };
    //for( j = m; j >= 1; j-- ) {
    //    mat[i][j] = value( i, j );
    //    if( j <= m - 1 )
    //        if( verif( i, j + 1 ) )
    //            return { i, j + 1 };
    //}

    //return { 1, 1 };

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