http://codeforces.com/contest/1080/problem/C
题意:
给你一个 n*m 的棋盘, 最初 (1,1) 上为白色, 而且每个相邻的块颜色都不同. 之后有两次操作, 第一次操作给出 x1,y2,x2,y2 将 (x1,y1,x2,y2) 这个矩形涂为白色第二次操作给出 x3,y3,x4,y4
将 (x3,y3,x4,y4) 这个矩形涂为黑色
后涂得会覆盖之前的颜色. 问最终的棋盘上黑色和白色的个数
解法:
可以发现, 矩形白色个数是由左下角的颜色和行数列数奇偶性决定的.
先算出原矩形白色个数,
加上黑变白的个数,
减去白变黑的个数.
如果两个矩形没有相交答案就是上述过程的答案.
如果有相交就是减去相交区域黑色的个数,
相当于黑变白的个数减少了.
- /*************************************************************************
- > File Name: 矩形面积交. cpp
- > Author: QWX
- > Mail:
- > Created Time: 2018/11/24 14:24:14
- ************************************************************************/
- //{{{ #include
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<vector>
- #include<cmath>
- #include<queue>
- #include<map>
- #include<set>
- #include<string>
- #include<cstring>
- #include<complex>
- #include<cassert>
- //#include<bits/stdc++.h>
- #define vi vector<ll>
- #define pii pair<ll,ll>
- #define mp make_pair
- #define pb push_back
- #define fi first
- #define se second
- #define pw(x) (1ll <<(x))
- #define sz(x) ((ll)(x).size())
- #define all(x) (x).begin(),(x).end()
- #define rep(i,l,r) for(ll i=(l);i<(r);i++)
- #define per(i,r,l) for(ll i=(r);i>=(l);i--)
- #define FOR(i,l,r) for(ll i=(l);i<=(r);i++)
- #define cl(a,b) memset(a,b,sizeof(a))
- #define fastio iOS::sync_with_stdio(false);cin.tie(0);
- #define lson l , mid , ls
- #define rson mid + 1 , r , rs
- #define INF 0x3f3f3f3f
- #define LINF 0x3f3f3f3f3f3f3f3f
- #define ll long long
- #define ull unsigned long long
- #define dd(x) cout <<#x << "=" << (x) << ","
- #define de(x) cout << #x << "=" << (x) << "\n"
- #define endl "\n"
- using namespace std;
- //}}}
- ll n,m;
- ll area(ll x1,ll y1,ll x2,ll y2)
- {
- ll a=x2-x1+1,b=y2-y1+1;
- ll ans=a*b/2;
- if(a*b%2!=0&&((x1+y1)%2==0))ans++;
- // dd(a),dd(b),de(ans);
- return ans;
- }
- ll cross(ll x1,ll y1,ll x2,ll y2,ll x3,ll y3,ll x4,ll y4)
- {
- ll lx=max(x1,x3);
- ll ly=max(y1,y3);
- ll rx=min(x2,x4);
- ll ry=min(y2,y4);
- if(lx>rx)return 0;
- if(ly>ry)return 0;
- ll a=rx-lx+1,b=ry-ly+1;
- ll ans=a*b/2;
- // dd(lx),dd(ly),dd(rx),dd(ry);dd(a),dd(b),de(ans);
- if(a*b%2!=0&&((lx+ly)%2==0))ans++;
- return a*b-ans;
- }
- int main()
- {
- ll T; cin>>T;
- while(T--){
- ll n,m; cin>>n>>m;
- ll x1,y1,x2,y2,x3,y3,x4,y4;
- cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
- ll s1=n*m/2+(n*m%2?1:0);
- ll s2=(x2-x1+1)*(y2-y1+1)-area(x1,y1,x2,y2);
- ll s3=area(x3,y3,x4,y4);
- ll s4=cross(x1,y1,x2,y2,x3,y3,x4,y4);
- ll ans=s1+s2-s3-s4;
- // dd(s1),dd(s2),dd(s3),de(s4);
- cout<<ans<<" "<<n*m-ans<<endl;
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2869888.html