[백준/BOJ] 백준 12002번 : Field Reduction (Silver)

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

12002번: Field Reduction (Silver)

 

소들 중 3개를 제거해서 가장 작은 직사각형을 만들어야 하므로, 제거하는 소는 끝에 있는 게 좋다. 그러므로, x좌표 기준으로 제일 작은 것 3개, 제일 큰 것 3개, y좌표 기준으로 제일 작은것 3개, 제일 큰 것 3개가 끝에 있는 점들이므로, 해당 점 중 3개를 제거하는 경우를 확인해서 제거한 점들을 제외한 나머지 점들을 둘러싸는 면적을 구하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
using namespace std;

int n;
vector<pair<int, int>> point; //(x,y)
vector<pair<int, int>> x_point; //(x,point번호)
vector<pair<int, int>> y_point; //(y,point번호)
int result = numeric_limits<int>::max();

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;

		int point_num = point.size();
		x_point.push_back(make_pair(x, point_num));
		y_point.push_back(make_pair(y, point_num));
		point.push_back(make_pair(x, y));
	}

	sort(x_point.begin(), x_point.end()); //x좌표 기준으로 정렬
	sort(y_point.begin(), y_point.end()); //y좌표 기준으로 정렬

	//소들 중 3개를 제거해서 직사각형을 작게 만들어야 하므로, 끝에 있는 점들중 3개를 고른다
	//x좌표 기준으로 제일 작은것 3개, 제일 큰것 3개,
	//y좌표 기준으로 제일 작은것 3개, 제일 큰것 3개,
	//후보중 3개를 뽑는다 
	vector<int> temp; //삭제할 후보

	for (int i = 0; i < 3; i++) {
		temp.push_back(x_point[i].second);
		temp.push_back(y_point[i].second);
		temp.push_back(x_point[n - 1 - i].second);
		temp.push_back(y_point[n - 1 - i].second);
	}

	//중복된 후보 제거
	sort(temp.begin(), temp.end());
	temp.erase(unique(temp.begin(), temp.end()), temp.end());

	vector<int> perm(temp.size(), 0);
	for (int i = 0; i < 3; i++) {
		perm[i] = 1;
	}
	sort(perm.begin(), perm.end());

	do {
		vector<int> remove_check(point.size(), 0); //삭제될 포인트 번호 체크
		for (int i = 0; i < perm.size(); i++) {

			int remove_num = temp[i];

			if (perm[i] == 1) { //temp[i]를 삭제할때
				remove_check[remove_num] = 1;
			}

		}

		int x_min = 987654321;
		int x_max = 0;
		int y_min = 987654321;
		int y_max = 0;
		for (int i = 0; i < point.size(); i++) {
			if (remove_check[i] == 1) {
				continue;
			}

			x_min = min(x_min, point[i].first);
			x_max = max(x_max, point[i].first);
			y_min = min(y_min, point[i].second);
			y_max = max(y_max, point[i].second);
		}

		int len1 = x_max - x_min;
		int len2 = y_max - y_min;
		result = min(result, len1 * len2);

	} while (next_permutation(perm.begin(), perm.end()));

	cout << result;

	return 0;
}