让大家都喝上水的最短距离.在一个平面上有n(1
来源：学生作业帮助网 编辑：六六作业网 时间：2024/05/10 02:18:04
让大家都喝上水的最短距离.在一个平面上有n(1
让大家都喝上水的最短距离.
在一个平面上有n(1
让大家都喝上水的最短距离.在一个平面上有n(1
不愿意想太多,既然没有时间和内存限制,直接暴力破解
#include <stdio.h>
int total;
long long map[100000][2];
long long calc_length(long long x, long long y)
{
long long ret = 0;
int i;
for(i = 0; i < total; i ++)
ret += abs(x - map[i][0]) + abs(y - map[i][1]);
return ret;
}
void main()
{
int i;
long long x, y, len, min_len;
long long min_x, min_y, max_x, max_y;
scanf("%d", &total);
for(i =0; i < total; i ++)
{
scanf("%lld%lld", &map[i][0], &map[i][1]);
if(i == 0)
{
min_x = max_x = map[0][0];
min_y = max_y = map[0][1];
}
else
{
if(min_x > map[i][0]) min_x = map[i][0];
if(min_y > map[i][1]) min_y = map[i][1];
if(max_x < map[i][0]) max_x = map[i][0];
if(max_y < map[i][1]) max_y = map[i][1];
}
}
for(x = min_x; x <= max_x; x ++)
for(y = min_y; y <= max_y; y ++)
{
len = calc_length(x, y);
if(x == min_x && y == min_y) min_len = len;
else if(min_len > len) min_len = len;
}
printf("%lld\n", min_len);
}