[C/C++ 백준 2381번] 최대 거리 (Gold 5)

https://www.acmicpc.net/problem/2381

2381번: 최대 거리

https://blog.naver.com/programmer18/220794470677

최대 거리 (Math)

도저히 모르겠어서 이 분의 설명을 참고했다.

모든 설명이 완벽한데, 이렇게 계산해도 괜찮은지 의문이 들긴 했다. 예를 들어 y-x의 최대와 최소의 차이를 구했는데 실제로는 그렇게 계산하면 안되는 두 좌표에 대해 구한거라면( a<b 이고 c<d인 )안되는거 아닐까?

 

물론 답은 그러면 안되지만, 어차피 그런경우 y+x의 최대와 최소 경우가 더 크게 나오기 때문에 상관없다.

 

짠

모든 두 점은 위의 경우로 분류할 수 있다 (일직선인 경우는 둘 중 어느 경우에 들어가도 상관없음). 각 점에 대해 위의 두가지 방법으로 계산했을때, 어차피 1번 경우인 점은 1번 식이 더 크게 나오고 2번 경우인 점들은 2번 식이 더 크게 나오기 때문에 계산을 어떻게 하든지간에 더 큰걸만 고르기만 하면 맞게 된다.

 

코드는 다음과 같다.

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int N, a, b, minsMax=-2000001, minsMin=2000001;
	int plusMax=-2000001, plusMin=2000001;
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d %d", &a, &b);
		if((b-a)<minsMin)
			minsMin = (b-a);
		if((b-a)>minsMax)
			minsMax = (b-a);
		if((b+a)<plusMin)
			plusMin = (b+a);
		if((b+a)>plusMax)
			plusMax = (b+a);
	}
	printf("%d",max(minsMax-minsMin, plusMax-plusMin));
}