NYOJ 7 街区最短路径问题

发布时间:2024-07-15 17:01

描述一个街区有很多住户,街区的街道只能为东西、南北两种方向。

住户只可以沿着街道行走。

各个街道之间的间隔相等。

用(x,y)来表示住户坐在的街区。

例如(4,20),表示用户在东西方向第4个街道,南北方向第20个街道。

现在要建一个邮局,使得各个住户到邮局的距离之和最少。

求现在这个邮局应该建在那个地方使得所有住户距离之和最小;

输入
第一行一个整数n<20,表示有n组测试数据,下面是n组数据;
每组第一行一个整数m<20,表示本组有m个住户,下面的m行每行有两个整数0 m行后是新一组的数据;
输出
每组数据输出到邮局最小的距离和,回车结束;
样例输入
2
3
1 1
2 1
1 2
5
2 9 
5 20
11 9
1 1
1 20
样例输出
2
44
找出分别找出横纵坐标的中位数。注意 坐标不可以是小数。。所以,如果有偶数个点的话,中位数不能取平均值,要分别算一下取哪个点距离最小。
 
 
  
#include 
#include 
#define min(a,b) ((a) > (b) ? (b) : (a))
int comp ( const void *a, const void *b )
{
    return * ( int * ) a - * ( int * ) b;
}   
int absv(int a)             //绝对值
{
    if(a>=0)
        return a;
    else
        return -a;
}
  
int main()
{
  
    void mindis( int x[],int y[],int m);
    int i;
    int n;
    int m;
    int x[20];
    int y[20];
      
  
    scanf(\"%d\",&n);
    while(n--)
    {
        scanf(\"%d\",&m);
        for (i=0;i

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号