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:

- if there are more buildings below (A < B), the main cable must be shifted down;
- if there are more buildings above (A > B), the main cable must be shifted up.

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.

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