当前位置: 首页 > news >正文

数对的最大曼哈顿距离[ABC178E] Dist Max

[ABC178E] Dist Max

题面翻译

给定平面上 N N N 个点,求出所有点对间的最大曼哈顿距离。

题目描述

二次元平面上に $ N $ 個の点があり、$ i $ 番目の点の座標は $ (x_i,y_i) $ です。 同じ座標に複数の点があることもあります。 異なる二点間のマンハッタン距離として考えられる最大の値はいくつでしょうか。

ただし、二点 $ (x_i,y_i) $ と $ (x_j,y_j) $ のマンハッタン距離は $ |x_i-x_j|+|y_i-y_j| $ のことをいいます。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ : $ $ x_N $ $ y_N $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

3
1 1
2 4
3 2

样例输出 #1

4

样例 #2

样例输入 #2

2
1 1
1 1

样例输出 #2

0

提示

制約

  • $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $
  • $ 1\ \leq\ x_i,y_i\ \leq\ 10^9 $
  • 入力はすべて整数

Sample Explanation 1

$ 1 $ 番目の点と $ 2 $ 番目の点のマンハッタン距離は $ |1-2|+|1-4|=4 $ で、これが最大です。

思路:要 求两数对之间的曼哈顿距离,我们应该知道曼哈顿距离的公式为|xi - xj| + |yi - yj| , 分四种情况讨论后最后可以求得我们只用考虑两种情况:

在这里插入图片描述

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
const int M = 1e9 + 7;
const int MOD = 998244353;
typedef long long ll;
typedef pair<ll,ll>PII;
typedef pair<double, double>PDD;int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};//曼哈顿距离化简绝对值之后最终可以化简为两种取最大的即可
PII p[N];
bool cmp1(PII a, PII b)
{return a.first + a.second < b.first + b.second;
}
bool cmp2(PII a, PII b)
{return a.first - a.second < b.first - b.second;
}
int main()
{int n;cin >> n;for(int i = 1; i <= n; i ++){cin >> p[i].first >> p[i].second;}sort(p + 1, p + 1 + n, cmp1);ll res = abs(p[n].second  + p[n].first) - abs(p[1].first + p[1].second);sort(p + 1, p + 1 + n, cmp2);res = max(res, abs(p[n].first - p[n].second - (p[1].first - p[1].second)));cout << res << endl;return 0;
}

http://www.mrgr.cn/news/62023.html

相关文章:

  • MATLAB锂电概率分布模型
  • 【Pytorch】Pytorch的安装
  • Java 实现协同过滤算法推荐算法
  • 智能合约分享
  • Spring Boot集成Milvus和deeplearning4j实现图搜图功能
  • HTML入门教程17:HTML块
  • -函数结构
  • 多传感器数字化分析系统
  • Docker 部署 Java 项目实践
  • Android Studio项目(算法计算器)
  • openMV固件库编译环境搭建Linux
  • Java 并发工具(12/30)
  • QT——TCP网络调试助手
  • 创建ODBC数据源SQLConfigDataSource函数的用法
  • gpio子系统-通过io来控制gpio
  • 刚刚买的域名被DNS劫持了怎么处理
  • Spring 设计模式之装饰器模式
  • Unreal5从入门到精通之如何解决在VR项目在头显中卡顿的问题
  • 基于vue框架的的家政预定服务系统4k26i(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。
  • 万圣节活动如何实现在线预约报名?
  • uniapp iOS打包证书过期——重新下载证书及更新文件
  • 设计模式 - 工厂方法模式
  • Shell变量与子串
  • Mac程序坞窗口预览的方法来了
  • Rust 力扣 - 59. 螺旋矩阵 II
  • 为什么美业必须要有一套专业的美业门店管理系统?美业SaaS系统收银系统拓客系统Java源码