Problem 1942. GJam 2014 China Rd B: Party

This Challenge is derived from GJam 2014 China Party. Small Case.

The Goal is determine the optimal Party House. Given a set of people to attend a party, select the home from this set that minimizes the total travel of people. People travel only NSEW, no diagonals, to reach the host's home. If multiple homes have equal distance then select the home with minimum X. If there are more than one with Min distance and equal Min X then choose the house with Min Y.

The input is an array that defines rectangles of partiers. One line of the array is [xmin,ymin,xmax,ymax]. Blocks do not overlap.

Input: [M], Bx4 matrix (B<=100). Total B area of <=1000

Output: [x,y,d] where [x,y] is Party House and d is everyone's total distance

Examples:

M   [x y d]
[0 0 2 2] [1 1 12]
[-1 2 -1 2;0 0 0 0;1 3 1 3] [-1 2 6]

Contest Performance: Best Delta Time of 16 minutes with 496 of 2010 able to process the small data set. The large data set was only achieved by 47 in the 3 hrs of contest duration.

Commentary:

1) The small can be solved by brute force since fewer than 1000 points require evaluation.
2) The large case, which is giving me fits, has up to 1,000,000 points to evaluate.
3) Graphing the small case with surf gives some unexpected asymmetric results relative to the simple centroid.