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

 

 

몇 달을 붙잡고 있었던 문제.. 드디어 해결~~

 

그동안 어디서 막혔냐면 계산할 때 겹치는 부분은 어떡할것인가...! 이거에 대해서 계속 고민하다가 결국 힌트 받아서 해결했다. 다시 생각해도 힌트 없었으면 못 풀 것 같은 문제였다ㅋㅋㅋㅋ 진짜 알면 푸는데 모르면 못 푸는 문제

 

이걸 넓이 계산으로 문제를 풀지 말고 사각형이 존재하는지 판단하는 걸로 풀면 편하다. 범위가 100밖에 안 되니깐 100*100 벡터를 만들어서 전부 0으로 초기화 하고, 사각형이 존재하면 그 부분은 1로 바꾼다. 마지막에 1의 개수만 세면 면적의 넓이를 구할 수 있다. 

 

너무 신선하고 기발하다! 이렇게도 풀 수 있구나. 전혀 다른 접근법이라 감도 못 잡았다ㅋㅋㅋ

 

 

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

int main() {
    vector<vector<int>> v(100, vector<int>(100, 0));
    
    for(int k = 0; k < 4; k++){
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        
        for(int i = x1; i < x2; i++){
            for(int j = y1; j < y2; j++){
                v[i][j] = 1;
            }
        }
        
    }
    
    int result = 0;
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < 100; j++){
            if(v[i][j] == 1)
                result++;
        }
    }
    
    printf("%d", result);
    
    return 0;
}

 

기초도 다 끝냈다~~

오예에에에

 

방학동안 열심히 백준 등수나 올려야겠다ㅋㅋㅋ