[C++] 백준 1569 : 사각형으로 가리기

#include <iostream>
using namespace std;

int main() {
	int N;
	int answer = -1;
	int L; //정사각형 한변의 길이
	int points[50][2]; // 모든 점의 좌표를 담을 배열
	cin >> N;

	int maxX = -1000;
	int maxY = -1000;
	int minX = 1000;
	int minY = 1000;

	int x, y;
	// 모든 점들에서 x좌표의 최댓값, y좌표의 최댓값을 구한다.
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		points[i][0] = x;
		points[i][1] = y;
		maxX = max(x, maxX);
		maxY = max(y, maxY);
		minX = min(x, minX);
		minY = min(y, minY);
	}

	L = max(maxX-minX,maxY-minY); // 정사각형 한변의 길이는 'x 좌표의 최대 최소의 차이'와 'y좌표 최대 최소의 차이' 중 작은값


	if (maxX - minX == maxY - minY) {
		//x최대최소차이 와 y최대최소 차이가 같을 때에는
		//모든 점들을 순회 하면서
		//정사각형 변에 절대 걸칠수 없는점 (모든 좌표가 최대 최소 값이 아닌 점) 이 하나라도 있다면
		// -1이 정답이 되게끔 한다.
		answer = L;
		for (int i = 0; i < N; i++) {
			if (points[i][0] != maxX && points[i][0] != minX && points[i][1] != maxY && points[i][1] != minY) {
				answer = -1;
			}
		}
	}else{
		//x최대최소차이 와 y최대최소 차이가 다를 때에는
		//x,y중 최대최소 차이가 작은쪽 축 기준으로 L+1개의 사각형을 만들 수 있다.
		int maxX_s, maxY_s, minX_s, minY_s; // 그때마다 최대 최솟값을 새로 정하기위해 선언한 변수들
		for (int i = 0; i <= L; i++) {
			if (maxX - minX > maxY - minY) {
				minY_s = maxY - i;
				maxY_s = minY_s + L;
				minX_s = minX;
				maxX_s = maxX;
			}
			else {
				minX_s = maxX - i;
				maxX_s = minX_s + L;
				minY_s = minY;
				maxY_s = maxY;
			}

			int cnt = 0;
			for (int i = 0; i < N; i++) {
				// 모든 점들이 사각형 위에 존재 하는지 검사한다.
				// 점의 x,y 좌표중 둘중 하나라도 최대 최소값이라면 (사각형에 걸쳐있다면)
				if (points[i][0] == maxX_s || points[i][0] == minX_s || points[i][1] == maxY_s || points[i][1] == minY_s) {
					cnt++;
				}
			}
			//모든 점들이 검사를 통과했다면 
			if (cnt == N) {
				answer = L;
			}
		}
	}

	cout << answer;
	return 0;
}

 

오랜만에 푼 클래식한 문제이다.

만만하게 봤는데 생각보다 생각할게 많았다.

여러개의 사각형이 만들어 질 수 있다는게 포인트였다.