[C++]BJO : 1117 : 색칠 1

문제

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

 

 

 

풀이

쌩 구현으로 푸는 문제이다. 주어진 테스트 케이스만으로는 고려할 수 없는 경우들이 있어서 case를 잘 구분해주어야 한다.

 

1. f를 기준으로 접었을 때 겹쳐지는 영역

2. f를 기준으로 접었을 때 겹쳐지지 않는 영역이 발생하는 경우

    a. 겹쳐지는 영역에 색칠되는 경우

    b.  겹쳐지지 않는 영역에 색칠되는 경우 

 

 

 

이렇게 각 경우에 대한 영역을 고려해서 계산한다.

 

이때 1과 2-a의 경우 f를 기준으로 접었을 때 반대쪽에 새롭게 색칠되지만, 2-b 의 경우 f를 기준으로 접었을 때 새로 색칠되는 영역이 없다.

 

만약 2-a와 2-b가 함께 존재하는 경우 2-a와 2-b를 각각 구해서 겹침으로 새롭게 색칠되는 영역과 단독으로 색칠되는 영역을 구분해주어야 한다.

 

자세한 내용은 코드의 주석을 확인하면 된다.

 

 

 

코드

#include <iostream>
using namespace std;

long W, H, f, c, x1, y1, x2, y2, ans;
int main() {
    cin >> W >> H >> f >> c >> x1 >> y1 >> x2 >> y2;

    // 실제 x 좌표는 f 기준으로 더해주어야 함.
    x1+=f; x2+=f;
    
    // area : f축 기준으로 겹치는 부분의 면적
    long area;
    if(x2 > W){
        if(x1 >= W) area = 0;
        else area = (W-x1)*(y2-y1);
    } 
    else area = (x2-x1)*(y2-y1);
    
    // H 까지 폴드 면적 우선 계산(겹치는 영역) : 영역당 한 번만 존재함.)
    ans+= (c+1)*area;
    
    // area_out : 겹치치 않는 영역 계산 
    long area_out = 0;
    if(x2 > W){
        if(x1 >= W){
            area_out = (x2-x1)*(y2-y1) * (c+1);
        }
        else{
            area_out = (x2-W)*(y2-y1) * (c+1);
        }
    }
  
    // f 기준 겹치는 반대쪽 영역 계산
    long x0 = f - (x1-f);
    long dx=0; // 해당 영역의 가로 길이
    if(x2 > W && x1 <W) dx = W - x1;
    else dx = x2 - x1; 

    long x_cnt = 0;
    long r = ans/(dx); // 세로 한 축당 색칠 영역
    for(long i=x0-1, j = 0; i>=0; i--, j++){
        if(j == dx) break;
        x_cnt++; // 색칠 가능 가로 영역 계산
    }
    
    ans += (x_cnt)*r;
    ans += area_out;
    cout << (W*H)-ans << "\n";

    return 0;
}

 

 

 

 

 

---

메모

분명 더 쉽게 풀 수 있는 방법.. 좀 더 간결하게 작성할 수 있는 방법이 있겠지만...
새롭게 생각나는 테케들을 위해 수정하다보니 이렇게 되어버렸다...