Luogu P5098 Cave Cows 3
题目大意
??有\(n\)个坐标\((x_i, y_i)\),求任意两个坐标之间的最大曼哈顿距离。
??\(1 \leq n \leq 50000\),\(-1 \times 10^6 \leq x1,x2,y1,y2 \leq 1 \times 10^6\)。
?
题解
??我们把\(|x_1 - x_2| + |y_1 - y_2|\)分成四种情况:
\[\left \{ \begin{matrix}
|x_1 - x_2| + |y_1 - y_2| = x_1 - x_2 + y_1 - y_2 = (x_1 + y_1) - (x_2 + y_2), \color{blue}{(x_1 \geq x_2, y_1 \geq y_2)}
\\ |x_1 - x_2| + |y_1 - y_2| = x_1 - x_2 + y_2 - y_1 = (x_1 - y_1) - (x_2 - y_2), \color{blue}{(x_1 \geq x_2, y_1 < y_2)}
\\ |x_1 - x_2| + |y_1 - y_2| = x_2 - x_1 + y_1 - y_2 = -((x_1 - y_1) - (x_2 - y_2)), \color{blue}{(x_1 < x_2, y_1 \geq y_2)}
\\ |x_1 - x_2| + |y_1 - y_2| = x_2 - x_1 + y_2 - y_1 = -((x_1 + y_2) - (x_2 + y_2)) , \color{blue}{(x_1 < x_2, y_1 < y_2)}
\end{matrix} \right.\]
??分别求\(x_i - y_i\)的最大值和最小值即可。
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int x, y;
int maxp = -(1 << 30), minp = 1 << 30, maxd = -(1 << 30), mind = 1 << 30;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &x, &y);
minp = min(minp, x + y);
maxp = max(maxp, x + y);
mind = min(mind, x - y);
maxd = max(maxd, x - y);
}
printf("%d", max(max(maxp - minp, -(maxp - minp)), max(maxd - mind, -(maxd - mind))));
return 0;
}
原文:https://www.cnblogs.com/kcn999/p/12238315.html