几何（geometry）
题目描述
小可可最近在学习平面几何!
给定平面上的
n
n
n个点
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
i
,
y
i
)
(x_1,y_1),(x_2,y_2),…,(x_i,y_i)
(x1,y1),(x2,y2),…,(xi,yi)。
根据题目要求，输出下列两个值其中一个:
- 任意两点间欧几里得距离最大值的平方，对于两个点
(
x
i
,
y
i
)
和
(
x
j
,
y
j
)
(x_i,y_i)和(x_j,y_j)
(xi,yi)和(xj,yj)，欧几里得距离定义为(
x
i
−
x
j
)
2
+
(
y
i
−
y
j
)
2
\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}
(xi−xj)2+(yi−yj)2。
2.任意两点间曼哈顿距离最大值，对于两个点
(
x
i
,
y
i
)
和
(
x
j
,
x
j
)
(x_i,y_i)和(x_j,x_j)
(xi,yi)和(xj,xj)，曼哈顿距离定义为
∣
x
i
−
x
j
∣
+
∣
y
i
−
y
j
∣
|x_i-x_j|+|y_i-y_j|
∣xi−xj∣+∣yi−yj∣。
输入格式
第一行，两个整数
n
,
o
p
，
n
n,op，n
n,op，n 为平面内有多少个点，
o
p
op
op 为1则求欧几里得距离最大值的平方，若
o
p
op
op 为2则求曼哈顿距离最大值。
第
2
到
n
+
1
2 到 n+1
2到n+1 行，每行两个数
x
i
,
y
i
x_i,y_i
xi,yi，表示平面上的一个点。
输出格式
一行，一个整数，表示答案。
样例 #1
样例输入 #1
5 1
3 4
1 2
5 2
3 1
2 3
样例输出 #1
16
样例 #2
样例输入 #2
5 2
3 4
1 2
5 2
3 1
2 3
样例输出 #2
4
提示
数据点1~2,op=1,
1
≤
n
<
1
0
3
,
1
<
x
i
<
1
0
4
,
y
i
=
1
1≤n<10^3,1<x_i< 10^4,y_i=1
1≤n<103,1<xi<104,yi=1。
数据点3~6,op=1,
1
≤
n
≤
1
0
3
,
1
≤
x
i
,
y
i
≤
1
0
9
1≤n≤10^3,1≤x_i,y_i≤ 10^9
1≤n≤103,1≤xi,yi≤109。
数据点 7~ 10，op=2,
1
≤
n
≤
1
0
3
,
1
≤
x
i
,
y
i
<
1
0
9
1≤n≤ 10^3,1≤x_i,y_i<10^9
1≤n≤103,1≤xi,yi<109。
数据点 11~ 14,op= 2,
1
≤
n
≤
1
0
6
,
1
≤
x
i
≤
1
0
9
,
y
i
=
1
1≤n≤ 10^6,1 ≤x_i≤ 10^9,y_i=1
1≤n≤106,1≤xi≤109,yi=1。
数据点 15~ 20，op=2,
1
≤
n
≤
1
0
6
,
1
≤
x
i
,
y
i
<
1
0
9
1≤n≤ 10^6,1≤ x_i,y_i< 10^9
1≤n≤106,1≤xi,yi<109。
#include
using namespace std;
const int N = 1e6 + 5;
int n, op, x[N], y[N];
int a = INT_MIN, b = INT_MAX, c = INT_MIN, d = INT_MAX;
int main() {
cin >> n >> op;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &x[i], &y[i]);
a = max(a, x[i] + y[i]);
b = min(b, x[i] + y[i]);
c = max(c, x[i] - y[i]);
d = min(d, x[i] - y[i]);
}
if (op == 1) {
long long ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
long long u = x[i] - x[j], v = y[i] - y[
j];
ans = max(ans, u * u + v * v);
}
cout << ans;
} else {
cout << max(a - b, c - d);
}
return 0;
}
