ABC_178_E - Dist Max

[zeikar]

Problem link

https://atcoder.jp/contests/abc178/tasks/abc178_e

Problem Summary

x, y 좌표가 주어질 때 가장 먼 맨해튼 거리를 구하는 문제.

Solution

일단 유명한 문제라고 하는데... 처음 대회에서는 풀지 못했다...

다시 천천히 해보면 어렵지 않은 문제이긴 하다

먼저 조건을 잘 써보면,| xi - xj | + | yi - yj |의 최댓값을 찾는 문제인데 절댓값을 벗겨준 후 정리해줄 수 있다.

1. xi > xj, yi > yj

(xi - xj) + (yi - yj)
(xi + yi) - (xj + yj)

2. xi < xj, yi > yj

-(xi - xj) + (yi - yj)
-(xi - yi) + (xj - yj)

3. xi > xj, yi < yj

(xi - xj) - (yi - yj)
(xi - yi) - (xj - yj)

4. xi < xj, yi < yj

-(xi - xj) - (yi - yj)
-(xi + yi) + (xj + yj)

잘 보면 양쪽이 (xj + yj) 또는 (xj - yj) 형식으로 정리가 되는데 x, y값의 합 또는 x, y의 값의 차를 전부 구하고 그중에 최대가 되도록 해주면 된다.

따라서 정답은 max( max(xi + yi) - min(xi + yi), max(xi - yi) - min(xi - yi) )

Source Code

#include <iostream>
#include <climits>
using namespace std;

int main() {
	int n;
	cin >> n;

	int maxPlus = -INT_MAX;
	int minPlus = INT_MAX;
	int maxMinus = -INT_MAX;
	int minMinus = INT_MAX;
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;

		int plus = x + y;
		int minus = x - y;

		maxPlus = max(maxPlus, plus);
		minPlus = min(minPlus, plus);
		maxMinus = max(maxMinus, minus);
		minMinus = min(minMinus, minus);
	}

	cout << max(maxPlus - minPlus, maxMinus - minMinus) << endl;
}