HackerEarth Highways problem solution

In this HackerEarth Highways problem solution, Some country X is a square of N x N cells. Its inhabitants use a coordinate system in which the lower-left and upper-right corners of the square have coordinates (0,0) and (N,N). There are K cities in the country, each at a point with integer coordinates.

Residents of country X move around the country parallel to the coordinate axes. To speed up travel to neighboring countries, the government has decided to build two highways. Highways must be perpendicular to each other and parallel to the coordinate axes. Each trunk will connect two opposite sides of the square.

The distance from the city to the highways will be the distance from the city to the nearest one. The government has decided to place highways so that the maximum distance from cities to highways is the minimum possible.

Your task is to find the optimal distance from the farthest city to the nearest highway.

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;
}

coding problems solutions