2015
05-23

# Meeting point-1

It has been ten years since TJU-ACM established. And in this year all the retired TJU-ACMers want to get together to celebrate the tenth anniversary. Because the retired TJU-ACMers may live in different places around the world, it may be hard to find out where to celebrate this meeting in order to minimize the sum travel time of all the retired TJU-ACMers.
There is an infinite integer grid at which N retired TJU-ACMers have their houses on. They decide to unite at a common meeting place, which is someone’s house. From any given cell, only 4 adjacent cells are reachable in 1 unit of time.
Eg: (x,y) can be reached from (x-1,y), (x+1,y), (x, y-1), (x, y+1).
Finding a common meeting place which minimizes the sum of the travel time of all the retired TJU-ACMers.

The first line is an integer T represents there are T test cases. (0<T <=10)
For each test case, the first line is an integer n represents there are n retired TJU-ACMers. (0<n<=100000), the following n lines each contains two integers x, y coordinate of the i-th TJU-ACMer. (-10^9 <= x,y <= 10^9)

The first line is an integer T represents there are T test cases. (0<T <=10)
For each test case, the first line is an integer n represents there are n retired TJU-ACMers. (0<n<=100000), the following n lines each contains two integers x, y coordinate of the i-th TJU-ACMer. (-10^9 <= x,y <= 10^9)

4
6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
6
0 0
2 0
-5 -2
2 -2
-1 2
4 0
5
-5 1
-1 3
3 1
3 -1
1 -1
10
-1 -1
-3 2
-4 4
5 2
5 -4
3 -1
4 3
-1 -2
3 4
-2 2

26
20
20
56
Hint
In the first case, the meeting point is (-1,-2); the second is (0,0), the third is (3,1) and the last is (-2,2)


/*

树状数组+二分(可以不用二分)。
果真是流年不利么。。。一开始就考虑会爆int的，就想到用64位了，

简单说下思路吧：
假设现在有n个点，把这些点都画到坐标纸上后第i个点在最左边、
同时也是最下面，
那么，假设大家都到i这里来：
第一个人到i这里，要走x1-xi+y1-yi;
第二个人到i这里，要走x2-xi+y2-yi;
。。。。。。
第n个人道i这里，要走 xn-xi+yn-yi;
(看出来思路没？)简单整合一下，不就是：
ans=(x1+x2+x3+…+xn)-n*xi+(y1+y2+…+yn)-n*yi;
(括号里面的sum部分可以用树状数组、线段树呀来维护)
但是，有些x<xi、有些x>xi，怎么办呢？那就将所有的x都排个序，
再将所有的y排个序，同时让每个x记住自己对应的y值在排序后到了哪儿，
在排序之后，再列出这个树状数组(线段树)。
然后对x从小到大遍历，遍历的当前的点就作为当前的中心，让大
家都来这个点，这个时候，刚刚的“(x1+x2+…+xn)”就可以分为两个部
分了，一部分在当前点左边，一部分在当前点右边，这个借助树状数组
在log(n)的时间内求出x方向上的ans_x；再找到当前点对应的y值，用同
样的方法求出y方向上的ans_y，然后就可以得到ans=ans_x+ans_y了。

PS：
打字打上瘾了。。。
头有点儿晕，就懒一下，没有维护排序后x对应的y在哪里，用的方法是
每次都二分查找一下-、-I，不过只是大概让时间*2了而已，仍在可以接受范
围以内。。。

2012-12-12
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define N 100011

int n;
struct A
{
int x,y;
}E[N];
int x[N],y[N];

int lowbit[N];
__int64 C[2][N];								//0x、1y

int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
void get_lowbit()
{
int i;
for(i=1;i<=100000;i++)    lowbit[i]=i&(-i);
}

__int64 sum(int K,int k)
{
__int64 p=0;
while(k>0 && k<=n)
{
p+=C[K][k];
k-=lowbit[k];
}
return p;
}
void update(int K,int k,int dir)
{
while(k>0 && k<=n)
{
C[K][k]+=dir;
k+=lowbit[k];
}
}
void init()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&E[i].x,&E[i].y);
x[i]=E[i].x;
y[i]=E[i].y;
}
x[0]=y[0]=-1111111111;
qsort(x,n+1,sizeof(int),cmp);
qsort(y,n+1,sizeof(int),cmp);
memset(C,0,sizeof(C));
for(i=1;i<=n;i++)
{
update(0,i,x[i]);
update(1,i,y[i]);
}
}
__int64 solve()
{
int i;
int low,mid,up;
__int64 a,b;
__int64 sum_x,sum_y;
__int64 temp,ans;
ans=100011;
ans*=1000000000;
sum_x=sum(0,n);
sum_y=sum(1,n);
for(i=1;i<=n;i++)
{
low=1;up=n;mid=(low+up)>>1;
while(low<=up)
{
if(x[mid]<E[i].x)    low=mid+1;
else                up=mid-1;
mid=(low+up)>>1;
}
a=sum(0,low);
temp=(__int64)low*E[i].x-a+sum_x-a-(n-(__int64)low)*E[i].x;
low=1;up=n;mid=(low+up)>>1;
while(low<=up)
{
if(y[mid]<E[i].y)    low=mid+1;
else                up=mid-1;
mid=(low+up)>>1;
}
b=sum(1,low);
temp+=(__int64)low*E[i].y-b+sum_y-b-(n-(__int64)low)*E[i].y;
if(temp<ans)    ans=temp;
}
return ans;
}

int main()
{
int T;
get_lowbit();
scanf("%d",&T);
while(T--)
{
init();
printf("%I64d\n",solve());
}
return 0;
}

1. 我看你有毛病，那个漫画女主角不长成这样，就你家凉夕好吗，当然，我也不是在骂凉夕，还有啊，我问你，凉席哪一话露大腿啦，你哪只眼睛看到搭！还有，你去看看二次元女神排行榜，你家凉席有叶冰瑶高吗，二次元CP榜，凉席和福临我都没找到

2. 我看你有毛病，那个漫画女主角不长成这样，就你家凉夕好吗，当然，我也不是在骂凉夕，还有啊，我问你，凉席哪一话露大腿啦，你哪只眼睛看到搭！还有，你去看看二次元女神排行榜，你家凉席有叶冰瑶高吗，二次元CP榜，凉席和福临我都没找到

3. 我看你有毛病，那个漫画女主角不长成这样，就你家凉夕好吗，当然，我也不是在骂凉夕，还有啊，我问你，凉席哪一话露大腿啦，你哪只眼睛看到搭！还有，你去看看二次元女神排行榜，你家凉席有叶冰瑶高吗，二次元CP榜，凉席和福临我都没找到

4. 我看你有毛病，那个漫画女主角不长成这样，就你家凉夕好吗，当然，我也不是在骂凉夕，还有啊，我问你，凉席哪一话露大腿啦，你哪只眼睛看到搭！还有，你去看看二次元女神排行榜，你家凉席有叶冰瑶高吗，二次元CP榜，凉席和福临我都没找到

5. 我看你有毛病，那个漫画女主角不长成这样，就你家凉夕好吗，当然，我也不是在骂凉夕，还有啊，我问你，凉席哪一话露大腿啦，你哪只眼睛看到搭！还有，你去看看二次元女神排行榜，你家凉席有叶冰瑶高吗，二次元CP榜，凉席和福临我都没找到