Codeforces Round #524(Div.2) C. Masha and two friends (1080C)

문제 링크 : https://codeforces.com/contest/1080/problem/C

사실 문제는 많이 어렵지 않았다. 결과 개수만 long long으로 하고 좌표를 long long으로 선언하지 않아서 계속 맞왜틀을 시전한 문제.

문제에 대한 자세한 내용은 링크를 통해 확인하기로 하고 해결한 방법은 다음과 같다. 우선, black과 white의 개수가 있다. 이 때, white의 개수는 무조건 전체 개수 - black 개수이다. 그러므로 black만 따져주도록 하자.

흰색 잉크를 쏟고 그 다음 검정색 잉크를 쏟는 순서이다.

- 먼저 원래 black이었던 칸의 개수를 구해준다.( 1,1이 w이므로 무조건 전체 칸 개수 / 2 )

- 다음은 흰색을 쏟은 상황이다. 흰색에 흰색을 쏟은 경우는 개수에 변화가 없으므로 무시한다. 즉, 원래 검정색이었던 칸에 흰색이 쏟아진 개수만 카운트한 후 현재 black 개수에서 빼준다.

- 다음은 검정색을 쏟은 상황이다. 이 때, 원래 검정색이었던 칸에 검정색을 쏟은 경우는 마찬가지로 무시한다. 원래 흰색이었던 칸에 검정색을 쏟은 경우만 카운트한 후 현재 black 개수에서 더해준다.

- 마지막으로 가장 중요한 부분이다. 흰색을 쏟았던 칸에 검정색을 겹쳐서 쏟은 경우를 따져야한다.
이 때, 나올 수 있는 경우의 수는 다음과 같다.

1. w -> w -> b
2. b  -> w -> b

1번의 경우는 결국 원래 흰색이었던 칸에 검정색을 쏟은 상황과 같다. 즉 이미 진행한 계산에 포함되어 있다. 그렇다면 따져줘야 하는 것은 원래 검정색이었던 칸에 흰색을 쏟고 다시 검정색을 쏟은 경우이다. 이 경우를 따지기 위해서는 겹치는 사각형의 영역을 알아야 한다. 이 영역을 구하는 방법은 다음과 같다.

출처 ;https://tibyte.kr/228

즉, 겹치는 사각형의 영역은 문제에서 x1과 x3중 큰 값, y1, y3중 큰 값이 시작점이 되고 마찬가지로 x2와 x4 중 작은 값, y2, y4중 작은 값이 끝 점이 되는 사각형이다.

만약 겹치는 사각형의 영역으로 나온 좌표가 시작점의 x,y좌표가 끝점의 x,y좌표보다 크다면 겹치는 영역이 없음을 의미한다. 이 방법으로 겹치는 영역에서 원래 검정색이었던 칸의 개수를 찾아서 더해준다. 최종적으로 나온 black 개수를 전체 칸 개수에서 빼주면 white도 정상적으로 구할 수 있다.

- 소스코드 -

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main() {
    int T;
    cin >> T;
    for (int test_case = 0; test_case < T; test_case++) {
        long long row, col;
        cin >> row >> col;
        long long x1, y1, x2, y2, x3, y3, x4, y4;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        long long black, white;
        black = (row*col) / 2;
        
        if ((x1 + y1) % 2 == 1) {
            black -= (((x2 - x1+1)*(y2 - y1+1)) / 2);
            if ((x2 - x1 + 1) % 2 == 1 && (y2 - y1 + 1) % 2 == 1) {
                black--;
            }
        }
        else {
            black -= (((x2 - x1+1)*(y2 - y1+1)) / 2);
        }
 
        if ((x3 + y3) % 2 == 1) {
            black += (((x4 - x3+1)*(y4 - y3+1)) / 2);
        }
        else {
            black += (((x4 - x3 + 1)*(y4 - y3 + 1)) / 2);
            if ((x4 - x3 + 1) % 2 == 1 && (y4 - y3 + 1) % 2 == 1) {
                black++;
            }
        }
        long long co_x1, co_x2, co_y1, co_y2;
        co_x1 = max(x1, x3);
        co_x2 = min(x2, x4);
        co_y1 = max(y1, y3);
        co_y2 = min(y2, y4);
        if (co_x2 >= co_x1&&co_y2 >= co_y1) {
            if ((co_x1 + co_y1) % 2 == 1) {
                black += ((co_x2 - co_x1 + 1)*(co_y2 - co_y1 + 1) / 2);
                if ((co_x2 - co_x1 + 1) % 2 == 1 && (co_y2 - co_y1 + 1) % 2 == 1) {
                    black++;
                }
            }
            else {
                black += ((co_x2 - co_x1 + 1)*(co_y2 - co_y1 + 1) / 2);
            }
        }
        white = (row*col) - black;
        cout << white << " " << black << "\n";
 
    }
 
    return 0;
}