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

문제링크 : https://www.acmicpc.net/problem/1438

1438번: 가장 작은 직사각형

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

bool compare(const pii &a, const pii &b)
{
    return a.second < b.second;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, result = MAX;
    pii p[100];

    cin >> N;

    for(int i=0; i<N; i++)
    {
        cin >> p[i].first >> p[i].second;
    }

    sort(p, p+N, compare); //y값 기준 정렬

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(i>j) continue;

            int x1 = p[i].first;  //fix한 x좌표 2개
            int x2 = p[j].first;

            if(x1>x2)
            {
                swap(x1, x2);
            }

            for(int k=0; k<N; k++)
            {
                int y1 = p[k].second;
                int cnt = 0;

                for(int l = k; l<N; l++)  //y값 늘려가며 체크
                {
                    int between_x = p[l].first;
                    int y2 = p[l].second;

                    if(x1<= between_x && between_x <= x2) //해당 좌표의 x가 fix한 x좌표의 사잇값인지 체크
                    {
                        cnt+=1;
                    }
                    if (cnt>=N/2)
                    {
                        result = min(result, (x2 - x1 + 2) * (y2 - y1 + 2)); //넓이 반환
                    }
                }
            }
        }
    }

    cout << result;

    return 0;
}

처음으로 푼 골드 2 문제이다.

푸는데 한계를 느껴서 친구의 도움을 받아 풀 수 있었다.

 

y좌표를 기준으로 정렬을 하고 시작한다

x좌표 2개를 고정시켜놓고 y좌표를 아래로 증가시켜가며 조건에 맞는 좌표를 찾는다.

이런 좌표가 N/2개 이상이라면 결과값에 가장 작은 값을 저장한다.