Algorithm/BOJ
[백준 2381] 최대거리
giiro
2020. 10. 5. 21:53
문제
2381번: 최대 거리
첫째 줄에 N이 주어진다. 다음 N개의 줄에는 각 점의 x, y좌표가 주어진다. 각 좌표의 범위는 -1,000,000이상 1,000,000이하이다.
www.acmicpc.net
풀이
절댓값을 풀어서 나오는 네 가지 경우는 아래의 꼴입니다.
1. $±((a + b) - (c + d))$
2. $±((a - b) - (c - d))$
각 식을 살펴보면 결국 두 점간의 거리를 구하는 게 x, y좌표 대, 소관계와 관계없이 좌표 간의 합(차)의 차이를 구하는 것과 같고, 이에 최대 거리를 구하는 것은 각 좌표 간 합(차)의 최대 값에서 최소 값을 빼는 것과 같습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int n, a, b;
vector<int> p, m;
int main() {
cin.tie(NULL); cout.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a >> b;
p.push_back(a + b);
m.push_back(a - b);
}
sort(p.begin(), p.end()), sort(m.begin(), m.end());
cout << max(p[n - 1] - p[0], m[n - 1] - m[0]);
}