[Codeforces 1080C] Masha and two friends

[Codeforces 1080C] Masha and two friends

문제 설명 : 

n*m크기의 체스판이 있다. 이 체스판에 두 사람이 흰색 물감과 검정색 물감을 쏟았다. 물감이 쏟아진 모양이 직사각형일 때 쏟고난 뒤에 체스판에 칠해진 흰색 칸과 검정색 칸의 수를 구하는 문제이다.

풀이 : 

처음에 풀 때는 엄청난 솔루션이 존재할 줄 알았는데, 그냥 단순 수학 문제이다. 흰색 물감이 칠해진 영역, 검정색 물감이 칠해진 영역, (만약 존재한다면) 두 물감이 겹치는 영역을 따로 구해서 전체 흰색, 검정색 수에 더하고 빼면 된다.

주의할 점 : 

영역에 있는 블럭의 수가 짝수개라면 흰색과 검정색 수가 같지만, (홀수)*(홀수) 영역이라면 블럭의 수가 홀수이므로 흰색과 검정색의 수가 1개 차이나게 된다. 이 부분에 대한 처리가 각각 45줄과 52줄에 나와있다. 흰색 영역은 (x좌표 + y좌표)가 짝수이므로 이럴 때 +1을 해주고, 검정색은 홀수일 때 +1을 해주면 된다.

배운 점 : 

두 사각형이 겹치는 경우, 그 상황을 어떻게 판별할 것인가에 대한 코드가 76줄에 나와있다. 단 한 줄만으로 판단이 가능한데, 사실 저 코드는 예전에 Reference에서 두 선분의 교차 여부 판별이라고 쓴 적이 있다. 사각형의 겹치는 여부는 선분의 상황에서 한 차원이 더 늘어난 것 뿐이다. 다시말해, 수직선 상에서는 x좌표만 비교했다면 사각형에서는 x좌표와 y좌표를 동시에 비교하면 된다. x좌표에서 교차하면서 y좌표에서 교차하면 그게 곧 사각형이 겹치는 상황이라는 뜻이다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
/****************************Contest Template******************************/
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
typedef long long ll;
typedef unsigned long long ull;
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
/****************************Contest Template******************************/
// const int SIZE=
 
 
ll W(ll x1,ll y1,ll x2, ll y2){
    ll result=(x2-x1+1)*(y2-y1+1);
 
    if(result%2 && (x1+y1)%2==0 && (x2+y2)%2==0) result=(result+1)/2;
    else result/=2;
    return result;
}
ll B(ll x1,ll y1,ll x2, ll y2){
    ll result=(x2-x1+1)*(y2-y1+1);
 
    if(result%2 && (x1+y1)%2 && (x2+y2)%2) result=(result+1)/2;
    else result/=2;
    return result;
}
 
 
int main(){
    int t;  scanf("%d",&t);
 
    while(t--){
        ll n,m; scanf("%lld %lld",&n,&m);
 
        ll x1,x2,x3,x4,y1,y2,y3,y4;
        scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
        scanf("%lld %lld %lld %lld",&x3,&y3,&x4,&y4);
 
        ll totalW=W(1,1,m,n),totalB=B(1,1,m,n);
 
        totalW=totalW+B(x1,y1,x2,y2);
        totalB=totalB-B(x1,y1,x2,y2);
 
        totalW=totalW-W(x3,y3,x4,y4);
        totalB=totalB+W(x3,y3,x4,y4);
 
        bool is_overlap=(max(x1,x3)<=min(x2,x4) && max(y1,y3)<=min(y2,y4));
        if(is_overlap){
            ll xx1=max(x1,x3),xx2=min(x2,x4);
            ll yy1=max(y1,y3),yy2=min(y2,y4);
 
            totalW=totalW-B(xx1,yy1,xx2,yy2);
            totalB=totalB+B(xx1,yy1,xx2,yy2);
        }   
        printf("%lld %lld\n",totalW,totalB);
    }
 
    return 0;
}