Network Cabling

The aim of this puzzle, is to minimize the length of cable used to connect a business park to the network, given the coordinates of all the building. There must be a main horizontal cable, and for each building a dedicated vertical cable from the building to the main cable.

If there are A buildings above it and B buildings below it, shifting it up increases the total length of vertical cables by B-A, and shifting it down increases this number by A-B. So to minimize the length:

Finally, the optimal positions for the main cable are the positions where A = B. That is why, the y-coordinate of the main cable must be a median of the set of y-coordinates of the building.

C

Once the array Ys of the y-coordinates of the N buildings, sorted (once again thanks to qsort, but you could use your own sorting function), the median is simply Ys[N/2].

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>

/* Comparison function between two long long integers
   return -1 if a<b, 1 if a>b, 0 if a=b */
int cmp (const void * a, const void * b){
    long long aa = *(long long*)a;
    long long bb = *(long long*)b;
    return aa<bb?-1:aa>bb?1:0;
}

int main()
{
    int N;
    scanf("%d", &N);
    
    long long xMin = LLONG_MAX;
    long long xMax = 0LL;
    long long x;
    long long Ys[N];
    
    // reading coordinates, storing Ys, computing xMin and xMax
    for (int i = 0; i < N; i++) {
        long x;
        scanf("%Ld %Ld", &x, Ys+i);
        if (x < xMin) xMin = x;
        if (x > xMax) xMax = x;
    }
    // sorting Ys in ascending order
    qsort(Ys, N, sizeof(long long), cmp);
    
    /* The main horizontal cable length is xMax-xMin
       To minimize the total length of vertical cables, its 
       y-coordinate of the main cable must be a median of Ys, Ys[N/2]*/
    long long res = xMax-xMin;
    for (int i = 0 ; i < N ; i++)
        res += abs(Ys[N/2]-Ys[i]);
        
    printf("%Ld\n", res);
}