0 人解决，5 人已尝试。
0 份提交通过，共有 15 份提交。
9.9 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
After travelling around for years, Salesman John has decided to settle. He wants to build a new house close to his customers, so he doesn’t have to travel as much any more. Luckily John knows the location of all of his customers.
All of the customers’ locations are at (distinct) integer coordinates. John’s new house should also be built on integer coordinates, which cannot be the same as any of the cus- tomers’ locations. Since John lives in a large and crowded city, the travelling distance to any customer is the Manhattan distance: |x - xi| + |y - yi|, where (x, y) and (xi, yi) are the coordinates of the new house and a customer respectively.
What is the number of locations where John could settle, so the sum of the distance to all of his customers is as low as posible?
On the first line an integer t (1 ≤ t ≤ 100): the number of test cases. Then for each test case:
1.One line with an integer n (1 ≤ n ≤ 2 000): the number of customers John has.
2.n lines with two integers xi and yi (-1 000 000 000 ≤ xi, yi ≤ 1 000 000 000): the coordinates of the i-th customer.
For each test case:
2 4 1 -3 0 1 -2 1 1 -1 2 -999888777 1000000000 1000000000 -987654321
10 4 3987543098 3975087573110998514
0 人解决，5 人已尝试。
0 份提交通过，共有 15 份提交。
9.9 EMB 奖励。