[백준] 1438번 : 가장 작은 직사각형 (C++)

1438번 : 가장 작은 직사각형

---

문제)

현수는 어떤 좌표 평면에 점을 N개 찍었다. 신기하게도, 모든 점은 음이 아닌 정수 좌표에만 찍혔다.

현수는 직사각형을 하나 그리려고 하는데, 직사각형의 꼭짓점은 모두 정수 좌표이고, 모든 변이 X축과 Y축에 평행한 직사각형을 그리려고 한다. 또, 직사각형의 내부에 현수가 찍은 점이 적어도 N/2개가 들어있는 직사각형을 그리려고 한다. 점이 직사각형의 변 위에 놓여져 있는 것은 내부에 있는 것이 아니다.

이러한 직사각형 중에 넓이가 가장 작은 직사각형의 넓이를 출력하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 점의 개수 N이 주어진다. N은 항상 짝수이며, 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 현수가 찍은 점의 정보가 X좌표 Y좌표 순으로 들어온다. 각각의 좌표는 10,000보다 작거나 같은 음이 아닌 정수이다. 모든 점은 중복되지 않는다.

 

 

 

출력 :

첫째 줄에 현수가 만든 직사각형 중 가장 넓이가 가장 작은 것의 넓이를 출력한다.

 

 

 

 

풀이)

// 1438. 가장 작은 직사각형
#include <iostream>
#include <vector>
#include <limits.h>
#include <set>
 
using namespace std;
 
int n;
vector<pair<int, int>> vec;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    vec.resize(n);
    set<int> X;
    set<int> Y;
 
    int a, b;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        vec[i].first = a;
        vec[i].second = b;
        X.insert(a);
        Y.insert(b);
    }
        
    // 겹치는 수가 없도록 set을 이용해서 X와 Y를 압축시켜주었다.
    vector<int> pointX = vector<int>(X.begin(), X.end());
    vector<int> pointY = vector<int>(Y.begin(), Y.end());
 
    // 2중 for문을 활용해 2개의 X를 골라주었고,
    int ans = INT_MAX;
    for (int i = 0; i < pointX.size(); i++)
    {
        for (int j = i; j < pointX.size(); j++)
        {
 
            // 2개의 X가 골라졌다면 투 포인터를 활용하여
            // 가장 최소로 조건을 만족하는 직사각형을 찾는다.
 
            int iLen = pointY.size();
            
            int s = 0;
            int e = 0;
 
            while (s < iLen && e < iLen)
            {
                int x1 = pointX[i];
                int x2 = pointX[j];
                int y1 = pointY[s];
                int y2 = pointY[e];
 
                x1--; y1--;
                x2++; y2++;
 
                int cnt = 0;
                for (int k = 0; k < n; k++)
                {
                    if (x1 < vec[k].first && vec[k].first < x2
                        && y1 < vec[k].second && vec[k].second < y2)
                    {
                        cnt++;
                    }
                }
 
                if (s - 1 == e)
                {
                    e++;
                    continue;
                }
 
                if (cnt < (n / 2))
                {
                    e++;
                }
                else
                {
                    ans = min(ans, (x2 - x1) * (y2 - y1));
                    s++;
                }
            }
        }
    }
 
    cout << ans;
 
 
    return 0;
}
 

 

---

출처 : https://www.acmicpc.net/problem/1438 

1438번: 가장 작은 직사각형