几何（geometry）

2024-06-05 01:28

文章标签 几何 geometry

本文主要是介绍几何（geometry），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

小可可最近在学习平面几何!

给定平面上的 $n$ 个点 $x_1,y_1),(x_2,y_2),…,(x_i,y_i)$ 。

根据题目要求，输出下列两个值其中一个:

任意两点间欧几里得距离最大值的平方，对于两个点 $x_i,y_i)和(x_j,y_j)$ ，欧几里得距离定义为 $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$ 。

2.任意两点间曼哈顿距离最大值，对于两个点 $x_i,y_i)和(x_j,x_j)$ ，曼哈顿距离定义为 $x_i-x_j|+|y_i-y_j|$ 。

输入格式

第一行，两个整数 $n, o p ， n$ 为平面内有多少个点， $o p$ 为1则求欧几里得距离最大值的平方，若 $o p$ 为2则求曼哈顿距离最大值。

第 $2 到 n + 1$ 行，每行两个数 $x_i,y_i$ ，表示平面上的一个点。

输出格式

一行，一个整数，表示答案。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

数据点1~2,op=1, $1≤n<10^3,1<x_i< 10^4,y_i=1$ 。

数据点3~6,op=1, $1≤n≤10^3,1≤x_i,y_i≤ 10^9$ 。

数据点 7~ 10，op=2, $1≤n≤ 10^3,1≤x_i,y_i<10^9$ 。

数据点 11~ 14,op= 2, $1≤n≤ 10^6,1 ≤x_i≤ 10^9,y_i=1$ 。

数据点 15~ 20，op=2, $1≤n≤ 10^6,1≤ x_i,y_i< 10^9$ 。

#include <bits/stdc++.h>
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;
}