PLONK - Where to Drink the Plonk?

no tags 

Consider a city bounded by a square, whose n horizontal and n vertical streets divide it into (n+1)2 square blocks. However, in tribute to the ancient traditions of the first dwellers (who tended to overindulge in alcohol), all the inhabitants live at crossroads. A group of friends would like to meet for an evening of merriment at the place of residence of one of them. With a good deal of foresight, anticipating the difficulties they might have getting back to their respective homes, they would like to meet in the house of the friend which minimises the total walking distance for all of them. Assume that everybody walks along the streets, turning only at crossroads, and the distance between any pair of adjacent crossroads is 1.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case the first line of input contains the integer n - the number of friends who want to meet (1<=n<=10000). The next n lines contain two integers each, the i-th being xi yi, standing for the x and y coordinates of the crossroads at which the i-th friend lives (0<=xi,yi<=100000).

Output

For each test case output the total distance covered by all friends when walking to the meeting place.

Example

Sample input:
1
7
1 3
3 2
3 5
6 9
10 1
12 4
5 7

Sample output:
39
Warning: large Input/Output data, be careful with certain languages

hide comments
Paul Draper: 2012-12-13 12:53:21

Just to clarify:
(1) The "n horizontal and n vertical streets" have no relationship to the n used later in the problem.
(2) The meeting place must be a house (given in the input).

Brian Bi: 2010-12-11 01:51:19

It would be interesting theoretically though to determine whether it can be done in O(N), if we assume no restrictions on the values of the coordinates. After all, it is possible to do so in the one-dimensional case, using the famous linear-time median-finding algorithm.

Sunny ElemeNt__..!: 2010-05-02 11:45:57

How to solve it without sorting?

Brian Bi: 2010-01-13 22:45:57

@madhav, you mean to say it can be solved without sorting?

madhav: 2009-04-06 23:30:53

Yes the problem can be solved in O(n). Sorry guys After sorting its O(N). and ofcourse sorting can be done in O(N) :D

Last edit: 2010-08-14 21:34:40
Ragavendra: 2009-03-04 05:51:55

O(nlogn) solution, there might be a faster algorithm


Added by:adrian
Date:2004-07-28
Time limit:6s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:based on a problem from the VII Polish Collegiate Team Programming Contest (AMPPZ), 2002