Cave Cows 3

题目描述

约翰的 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 
#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;
	cin>>n;
	
	for(int i = 1; i <= n; i++)
		cin>>a[i].x>>a[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));
	}
	
	cout<
	
	return 0;
}