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

문제 출처 :

 

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 직사각형 넓이 표현

2. 겹쳐진 직사각형 넓이 표현

3. 총 면적 합 구하기

이러한 문제의 접근은 메모리 공간을 이용함으로써 효율적으로 해결 할 수 있다.

배열에 좌표점을 이용한 직사각형을 그려넣은 뒤 겹쳐지는 곳을 계속 1씩 더해주면 된다.

( ex   111 겹쳐지면 1121 이런식으로 표현한다. 2는 겹쳐진 부분을 의미)

        111             1121

소스 코드를 보면 이해가 더 쉬워질 것이다. 

소스 코드 : 

#include <stdio.h>
 
int map[101][101] = { 0, };
int i, j;
 
void draw()
{
    int a, b, c, d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    for (i = b; i < d; i++)
    {
        for (j = a; j < c; j++)
            map[i][j] ++;
    }
}
int main()
{
    int total = 0;
    draw();
    draw();
    draw();
    draw();
    
 
    for (int i = 0; i < 101; i++)
    {
        for (int j = 0; j < 101; j++)
        {
            if (map[i][j] >= 1)
                total++;
        }
        
    }
 
    printf("%d", total);
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>