AtCoder Beginner Contest 178 E
E - Dist Max 曼哈顿距离最大点对
\(ans = max(|x_i-x_j|+|y_i-y_j|)\)
考虑去绝对值,4种情况。sort一下取max即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int x[N],y[N];
int p[4][N];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i = 1;i <= n;i++)
{
cin>>x[i]>>y[i];
p[0][i]=x[i]+y[i];
p[1][i]=-x[i]+y[i];
p[2][i]=x[i]-y[i];
p[3][i]=-x[i]-y[i];
}
for(int i = 0;i < 4; i++)sort(p[i]+1,p[i]+1+n);
int mx = 0;
for(int i = 0;i < 4; i++)
{
mx = max(mx,p[i][n]-p[i][1]);
}
cout<<mx<<endl;
return 0;
}
- Beginner AtCoder Contest 178beginner atcoder contest 178 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315