[백준/BOJ] 9063번 대지 (C/C++)

백준 온라인 저지(BOJ) 9063번 대지
https://www.acmicpc.net/problem/9063

9063번: 대지

* 사용언어 : C언어, C++

 

1. 문제

N 개의 점 위치(2차원 정수)를 입력받고
모든 점을 둘러싸는 최소 크기의 직사각형의 넓이를 출력

이 경우 (5 - 2) * (4 - 1) = 9 출력

 

2. 풀이

입력받은 점 x, y 를 함께 고려하지 말고,
x, y 를 각각 나누어 생각해보면 쉽게 풀 수 있습니다.
 
위 그림에서 직사각형의 위쪽 선분은 모든 y 좌표 중 가장 큰 값에 위치합니다.
반대로 직사각형의 아래쪽 선분은 모든 y 좌표 중 가장 작은 값에 위치합니다.
그리고 이는 x 와 무관하게 독립적으로 드러나는 특성입니다.
(모든 점을 y 축으로 정사영했다고 가정하고 보면 이해하기 쉽습니다)
 
마찬가지로 직사각형의 왼쪽, 오른쪽 선분의 위치도
x 좌표의 최대값, 최소값으로 구할 수 있습니다.
 
 
최대, 최소를 찾기 위해서 정렬 or 자료구조를 쓰지는 않았고,
단순하게 입력을 받으면서 즉시 최대, 최소를 판별하는 방식으로 구현했습니다.
 
그 외 풀이는 아래 코드 참고하시면 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
9063_대지
1112KB	16ms
*/
#include <cstdio>

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n;
	scanf("%d", &n);

	int x, y, max_x = -10001, max_y = -10000, min_x = 10001, min_y = 10001;
	while (n--) {
		scanf("%d %d", &x, &y);
		if (x > max_x) max_x = x;
		if (y > max_y) max_y = y;
		if (x < min_x) min_x = x;
		if (y < min_y) min_y = y;
	}

	printf("%d\n", (max_x - min_x) * (max_y - min_y));
	return 0;
}