题意: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; }