codeforces 1080 C. Masha and two friends

题意:n*m矩形,被人泼一次白漆,又被泼一次黑漆。问结果白黑数量。

首先,xy交换一下,矩形变成左上-右下表示法。记录结果白记为num1,黑num2。泼之前黑白数量很好确定。矩形内黑白数量也很好确定。先减去2个矩形内黑白数量。记录矩形面积白area1,黑area2。

如果不重合,加上两个面积就行。

如果矩形2包含矩形1,那么之前矩形1减去的在加回来(因为减了2次)。num2+=area2。

如果矩形1包含矩形2。那么之前矩形2减去的在加回来(因为减了2次)。num1+=area1-area2。num2+=area2。

否则就是相交。取矩形上界小者,下界大者,左界右者,右界左者。如果边长<=0,不相交。否则交的部分加回来。再分别加上不重合部分。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
#define mkp make_pair
#define err cout<<"err"<<endl
using namespace std;
const double EPS=1e-8;
typedef long long lon;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const lon SZ=300010,SSZ=SZ*SZ,APB=4,one=1;
const lon INF=0x3f3f3f3f,mod=1000000007;
lon n,m;

void init()
{
    cin>>n>>m;
    //swap(n,m);
    lon w=n*m/2+((n*m)&1),b=n*m/2;
    lon x1,y1,x2,y2;
    lon x3,y3,x4,y4;
    cin>>x1>>y1>>x2>>y2;
    cin>>x3>>y3>>x4>>y4;
    swap(x1,y1),swap(x2,y2);
    swap(x3,y3),swap(x4,y4);
    lon dx=x2-x1+1,dy=y2-y1+1;
    lon w1=dx*dy/2,b1=dx*dy/2;
    //cout<<"w: "<<w<<" "<<b<<endl;
    if((dx*dy)&1)
    {
        if((x1+y1)&1)++b1;
        else ++w1;
    }
    lon area1=dx*dy;
    w-=w1,b-=b1;
    //cout<<"w: "<<w<<" "<<b<<endl;
    dx=x4-x3+1,dy=y4-y3+1;
    lon w2=dx*dy/2,b2=dx*dy/2;
    if((dx*dy)&1)
    {
        if((x3+y3)&1)++b2;
        else ++w2;
    }
    w-=w2,b-=b2;
    //cout<<"w: "<<w<<" "<<b<<endl;
    lon area2=dx*dy;
    if(x1>=x3&&x2<=x4&&y1>=y3&&y2<=y4)
    {
        w+=w1,b+=b1;
        b+=area2;
    }
    else if(x3>=x1&&x4<=x2&&y1<=y3&&y4<=y2)
    {
        w+=w2,b+=b2;
        w+=area1-area2;
        b+=area2;
    }
    else
    {
        if(y1>y3)
        {
            swap(x1,x3);
            swap(y1,y3);
            swap(x2,x4);
            swap(y2,y4);
        }
        //cout<<"err: "<<y3<<" "<<y2<<" "<<y4<<endl;
        lon x5,y5,x6,y6,w3,b3;
        x5=max(x1,x3),y5=max(y1,y3),x6=min(x2,x4),y6=min(y2,y4);
        dx=x6-x5+1,dy=y6-y5+1;
        w3=dx*dy/2,b3=dx*dy/2;
        lon area3=dx*dy;
        //cout<<"area: "<<x1<<" "<<x2<<" "<<x3<<" "<<x4<<" "<<dx<<" "<<dy<<endl;
        if((dx*dy)&1)
        {
            if((x5+y5)&1)++b3;
            else ++w3;
        }
        if(dx>=1&&dy>=1)
        {
            w+=w3,b+=b3;
            w+=area1,b+=area2,w-=area3;
        }
        else w+=area1,b+=area2;
        //cout<<"w3: "<<w3<<" "<<b3<<" "<<x5<<" "<<y5<<endl;
    }
    cout<<w<<" "<<b<<endl;
}

void work()
{
    
}

void release()
{
    
}

int main()
{
    std::ios::sync_with_stdio(0);
    //freopen("d:\\1.txt","r",stdin);
    lon casenum;
    cin>>casenum;
    //cout<<casenum<<endl;
    for(lon tim=1;tim<=casenum;++tim)
    //for(lon tim=1;cin>>n;++tim)
    {
        //cout<<"Case #"<<tim<<": ";
        for(int i=1;i<=1e7;++i);
        init();
        work();
        release();
    }
    return 0;
}

 

上一篇:AT3965 题解


下一篇:codeforces 1175 D. Array Splitting