【洛谷】AT_abc178_e [ABC178E] Dist Max 的题解
【洛谷】AT_abc178_e [ABC178E] Dist Max 的题解
洛谷传送门
AT传送门
题解
一道挺好玩的数学题 qaq，直接让我想起了数学月考的数学题，神奇曼哈顿距离 qaq。
首先，曼哈顿距离的计算公式是 d i s = ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ dis = \left| x_1 - x_2\right| + \left| y_1 - y_2\right| dis=∣x1−x2∣+∣y1−y2∣。
然后将曼哈顿公式推导可得
-
当 x 1 > x 2 x1 > x2 x1>x2 并且 y 1 > y 2 y1 > y2 y1>y2 时， d = ( x 1 − x 2 ) + ( y 1 − y 2 ) = ( x 1 + y 1 ) − ( x 2 − y 2 ) d = (x_1 − x_2) + (y_1 − y_2) = (x_1 + y_1) − (x_2 − y_2) d=(x1−x2)+(y1−y2)=(x1+y1)−(x2−y2)。
-
当 x 1 > x 2 x1 > x2 x1>x2 并且 y 1 < y 2 y1 < y2 y1<y2 时， d = ( x 1 − x 2 ) + ( y 2 − y 1 ) = ( x 1 + y 1 ) − ( x 2 − y 2 ) d = (x_1 − x_2) + (y_2 − y_1) = (x_1 + y_1) − (x_2 − y_2) d=(x1−x2)+(y2−y1)=(x1+y1)−(x2−y2)。
-
当 x 1 < x 2 x1 < x2 x1<x2 并且 y 1 > y 2 y1 > y2 y1>y2 时， d = ( x 2 − x 1 ) + ( y 1 − y 2 ) = ( x 2 + y 2 ) − ( x 1 − y 1 ) d = (x_2 − x_1) + (y_1 − y_2) = (x_2 + y_2) − (x_1 − y_1) d=(x2−x1)+(y1−y2)=(x2+y2)−(x1−y1)。
-
当 x 1 < x 2 x1 < x2 x1<x2 并且 y 1 < y 2 y1 < y2 y1<y2 时， d = ( x 2 − x 1 ) + ( y 2 − y 1 ) = ( x 2 + y 2 ) − ( x 1 + y 1 ) d = (x_2 − x_1) + (y_2 − y_1) = (x_2 + y_2)- (x_1 + y_1) d=(x2−x1)+(y2−y1)=(x2+y2)−(x1+y1)。
根据上面的式子可以推得，曼哈顿距离的最大值为横纵坐标相加或相减后的值的较大点减去较小点。
所以，要让曼哈顿距离最大，就要让较大的数最大，较小的数最小。
最后输出即可，时间复杂度位 O ( n ) O(n) O(n)。
代码
#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {inline int read() {register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;}inline void write(int x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');return;}
}
using namespace fastIO;
int n, x, y;
int maxx = -999999999, maxy = -999999999, minx = 999999999, miny = 999999999;
int main() {//freopen(".in","r",stdin);//freopen(".out","w",stdout);n = read();for(int i = 1; i <= n; i ++) {x = read(), y = read();maxx = max(maxx, x + y);maxy = max(maxy, x - y);minx = min(minx, x + y);miny = min(miny, x - y);}write(max(maxx - minx, maxy - miny)), putchar('\n');return 0;
}