距离多点距离最近的点 中位数 boj1424

RobotSubmit: 218   Accepted:85Time Limit: 2000MS  Memory Limit: 65536KDescription
dalong 有一个n * n的棋盘，棋盘上有m个机器人。机器人分布在棋盘中不同的格子上，当然，有可能多个机器人在同一个棋盘上，每一次dalong可以对任意一个机器人操作， 使机器人向相邻的方向走一步（上下左右四个方向），当然，不能使机器人走出棋盘外。现在Dalong需要把所有的机器人移动到同一个位置（在哪个位置无所 谓，棋盘中任意一个格子都可），由于移动机器人需要耗费dalong一定的精力，因此他希望移动的总次数越少越好，你能帮助他吗？
下图是一个5*5的棋盘，有三个机器人，分别在（1，1）， （1 ， 2） ， （1 ， 4）

如果要把这三个机器人移到（1，2）这个格子中，一共需要3步：
1号机器人移动到（1，2）花费1步
2号机器人不移动
3号机器人移动到（1，2）花费2步
这是最少的移动步数


Input
输入的第一行是一个正整数m(m <= 50)，表示棋盘中机器人的个数。
后面m行，每行2个数x，y，第i+1行表示第i个机器人在棋盘的位置，其中棋盘标号横向从左到右依次是1，2，…….n,纵向从上到下依次是 1，2，…..n，机器人坐标x,y的范围(1 <= x,y <= n)，其中1 <= n <= 1000000;


Output
只有一行，最小的移动次数。保证答案小于2^31.


Sample Input

3
1 1
1 2
1 4


Sample Output

3


Hint
输入样例2
4
15 16
16 15
14 15
15 14
输出样例 2
4
输入样例3
2
4 7
4 7
输出样例 3
0



1424
此题主要用到了分治的思想,还有一个简单的定理:
 
到线段AB的距离和最小的点必然在线段AB之间
 
所以可以分别求到所有横坐标距离之和最小的x值,
和到所有纵坐标距离和最小的y值,
然后计算出结果
 
求x和y就用到了这个定理
先把所有x从小到大排序,
x[0],x[1],x[2],...x[n-1]
取位于线段x[0]x[n-1],x[1]x[n-2],x[2]x[n-3].....
之间的x值即为所求
这里可以取下标为中位数那个x[i]即为所求的x
y的求法同理

什么是中位数：
将数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值 　


#include 
#include 

int xx[60], yy[60];

int cmp(const void *a, const void *b)
{
    int *pa = (int *)a;
    int *pb = (int *)b;
    return *pa - *pb;
}

unsigned int find_steps(int x_mid, int y_mid, int size)
{
    unsigned int i, sum;

    sum = 0;
    for (i=0 ; i    {
        sum += (abs(xx[i] - x_mid) + abs(yy[i] - y_mid));
    }
    return sum;
}

int main(int argc, char *argv[])
{
    int m, i, x, y, x_mid, y_mid;
    unsigned steps;

    scanf("%d", &m);
    for (i=0 ; i    {
        scanf("%d %d", &xx[i], &yy[i]);
    }
    qsort(xx, m, sizeof(int), cmp);
    qsort(yy, m, sizeof(int), cmp);
    /*求出x,y方向上的中位数*/
    if (0 != m % 2)
    {
        x_mid = xx[m / 2];
        y_mid = yy[m / 2];
    }
    else
    {
        x_mid = (xx[m/2 - 1] + xx[m / 2]) / 2;
        y_mid = (yy[m/2 - 1] + yy[m / 2]) / 2;
    }
    /*求出所有点距离中位数的距离之和*/
    steps = find_steps(x_mid, y_mid, m);
    printf("%d\n", steps);
}