蚌埠网站建设蚌埠,东莞企业网站,直接用ip地址的网站怎么做,服务称赞的建筑机电网题目描述
约翰的 N (1≤N≤50000 )只牛在一个黑魃魃的洞里探险#xff0c;他们只能通过叫声交流。
两只牛之间的曼哈顿距离决定了声音传播的时间。即牛1与牛2交流#xff0c;需要的时间为 ∣x1−x2∣∣y1−y2∣ 。其中 −2≤106−106≤x1,x2,y1,y2≤106 。…题目描述
约翰的 N (1≤N≤50000 )只牛在一个黑魃魃的洞里探险他们只能通过叫声交流。
两只牛之间的曼哈顿距离决定了声音传播的时间。即牛1与牛2交流需要的时间为 ∣x1−x2∣∣y1−y2∣ 。其中 −2≤106−106≤x1,x2,y1,y2≤106 。
那任意一对牛之间交流时间的最大值为多少
输入格式
第1行输入 N 接下来每行输入一只牛的坐标。
输出格式
交流时间最大值即最大曼哈顿距离。
样例输入
5
1 1
3 5
2 7
8 1
4 4
样例输出
12
说明/提示
样例解释
(2,7)(2,7) 和 (8,1)(8,1) 两点间的距离最大为12。
参考代码
#include bits/stdc.h
#define ll long long
using namespace std;struct node
{int x;int y;
} a[50005];int mhd(int x1, int y1, int x2, int y2)
{return abs(x1 - x2) abs(y1 - y2);
}int main()
{int maxx 0, n;cinn;for(int i 1; i n; i)cina[i].xa[i].y;int heMax 0, heMin 0x3f3f3f3f;int chaMax 0, chaMin 0x3f3f3f3f;for(int i 1; i n; i){if(a[i].x a[i].y heMax){heMax a[i].x a[i].y;} if(a[i].x - a[i].y chaMax) {chaMax a[i].x - a[i].y;}if(a[i].x a[i].y heMin) {heMin a[i].x a[i].y;}if(a[i].x - a[i].y chaMin){chaMin a[i].x - a[i].y;}int s1, s2;s1 heMax - heMin;s2 chaMax - chaMin ;maxx max(maxx, max(s1, s2));}coutmaxx; return 0;
}
