백준 2669번 : 직사각형 네개의 합집합의 면적 구하기 (C 언어)

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

2669번: 직사각형 네개의 합집합의 면적 구하기

Code:

#include <stdio.h>
#include <limits.h>
 
int main()
{
    int check[101][101] = { 0, };
    int count = 4;
    int x1, y1, x2, y2;
    int maxx=INT_MIN, maxy=INT_MIN;
    while (count--)
    {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        for (int i = y1; i < y2; i++)
        {
            for (int j = x1; j < x2; j++)
            {
                if (check[i][j] == 1)
                {
                    continue;
                }
                else
                {
                    check[i][j] = 1;
                }
            }
        }
        if (maxx < x2)
        {
            maxx = x2;
        }
        if (maxy < y2)
        {
            maxy = y2;
        }
    }
    count = 0;
    for (int i = 0; i <= maxy; i++)
    {
        for (int j = 0; j <= maxx; j++)
        {
            if (check[i][j] == 1)
            {
                count++;
            }
            else
            {
                continue;
            }
        }
    }
    printf("%d", count);
}

문제 설명

이 문제는 네 개의 직사각형이 주어졌을 때, 이 네 개의 직사각형이 차지하는 면적을 구하는 문제입니다. 주어진 네 개의 직사각형은 서로 겹칠 수 있고, 변이나 꼭짓점이 겹칠 수도 있습니다.

알고리즘 설명

해당 문제를 해결하기 위해 다음과 같은 알고리즘을 사용했습니다:

1. 네 개의 직사각형의 위치를 입력으로 받습니다.
2. 각 직사각형의 좌표 범위를 순회하며 해당 좌표를 표시하는 2차원 배열을 초기화합니다.
3. 각 직사각형을 순회하면서 해당하는 좌표를 2차원 배열에 표시합니다. 이미 표시된 좌표는 건너뜁니다.
4. 네 개의 직사각형 중 가장 오른쪽 위 꼭짓점의 x좌표와 y좌표를 구합니다.
5. 표시된 좌표를 순회하면서 직사각형이 차지하는 면적을 카운트합니다.
6. 최종적으로 계산된 면적을 출력합니다.