HackerEarth Highways problem solution

#include <bits/stdc++.h>

using namespace std;

struct Town{
    int x;
    int y;
};

vector<Town> towns;
vector<int> MinYFromBegin, MaxYFromBegin, MinYFromEnd, MaxYFromEnd;
int n, m, x, y, length, MinDistance, MaxDistance, XAnswer, YAnswer;

bool comp( Town a, Town b ){
    return ( a.x < b.x );
}

long long min( long long x, long long y ){
    return ( x < y ) ? x : y;
}

long long max( long long x, long long y ){
    return ( x > y ) ? x : y;
}

bool check( int distance ){
    int i = 0;
    int j = 0;
    int MinY, MaxY;
    while ( ( i < m || j < m ) ){
        bool change = false;
        if ( i == 0 && j == 0 ){
            MinY = MinYFromEnd[i+1];
            MaxY = MaxYFromEnd[i+1];
        } else if ( i == 0 && j == m-1 ){
            MinY = MaxY = 0;
        } else if ( i == 0 && j < m-1 ){
            MinY = MinYFromEnd[j+1];
            MaxY = MaxYFromEnd[j+1];
        } else if ( i > 0 && j == m-1 ){
            MinY = MinYFromBegin[i-1];
            MaxY = MaxYFromBegin[i-1];
        } else {
            MinY = min( MinYFromBegin[i-1], MinYFromEnd[j+1] );
            MaxY = max( MaxYFromBegin[i-1], MaxYFromEnd[j+1] );
        }
        if ( ( MaxY-MinY <= 2*distance ) && ( towns[j].x - towns[i].x <= 2*distance ) ){
            XAnswer = min( towns[i].x + distance, n );
            YAnswer = min( MinY + distance, n );
            return true;
        }
        if ( towns[j].x - towns[i].x <= 2*distance ){
            if ( j < m-1 ){
                j++;
                change = true;
            }
        } else {
            if ( i < m-1 ){
                i++;
                change = true;
            }
        }
        if ( !change ){
            return false;
        }
    }
}

int main(){
    scanf( "%d %d", &n, &m );
    for ( int i = 0; i < m; i++ ){
        scanf( "%d %d", &x, &y );
        Town t;
        t.x = x;
        t.y = y;
        towns.push_back( t );
    }
    sort( towns.begin(), towns.end(), comp );
    MinYFromBegin.push_back( towns[0].y );
    MaxYFromBegin.push_back( towns[0].y );
    for ( int i = 1; i < m; i++ ){
        MinYFromBegin.push_back( min( MinYFromBegin[i-1], towns[i].y ) );
        MaxYFromBegin.push_back( max( MaxYFromBegin[i-1], towns[i].y ) );
    }
    MinYFromEnd.resize( m );
    MaxYFromEnd.resize( m );
    MinYFromEnd[m-1] = towns[m-1].y;
    MaxYFromEnd[m-1] = towns[m-1].y;
    for ( int i = m-2; i >= 0; i-- ){
        MinYFromEnd[i] = min( MinYFromEnd[i+1], towns[i].y );
        MaxYFromEnd[i] = max( MaxYFromEnd[i+1], towns[i].y );
    }
    MinDistance = -1;
    MaxDistance = n;
    while ( MaxDistance - MinDistance > 1 ){
        length = ( MaxDistance + MinDistance ) / 2;
        if ( check( length ) ){
            MaxDistance = length;
        } else {
            MinDistance = length;
        }
    }
    printf( "%dn", MaxDistance);
    return 0;
}