C. Masha and two friends
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, Masha was presented with a chessboard with a height of

The rows on the chessboard are numbered from

Let us call a rectangle with coordinates

The chessboard is painted black and white as follows: An example of a chessboard. Masha was very happy with the gift and, therefore, invited her friends Maxim and Denis to show off. The guys decided to make her a treat — they bought her a can of white and a can of black paint, so that if the old board deteriorates, it can be repainted. When they came to Masha, something unpleasant happened: first, Maxim went over the threshold and spilled white paint on the rectangle

To spill paint of color

Masha was shocked! She drove away from the guests and decided to find out how spoiled the gift was. For this, she needs to know the number of cells of white and black color. Help her find these numbers!

Input

The first line contains a single integer

Each of them is described in the following format:

The first line contains two integers

The second line contains four integers

The third line contains four integers

Output

Output

Example
input
Copy
5
2 2
1 1 2 2
1 1 2 2
3 4
2 2 3 2
3 1 4 3
1 5
1 1 5 1
3 1 5 1
4 4
1 1 4 2
1 3 4 4
3 4
1 2 4 2
2 1 3 3

output
Copy
0 4
3 9
2 3
8 8
4 8

n1=min(max(x1,x2),max(x3,x4));
m1=min(max(y1,y2),max(y3,y4));
n2=max(min(x1,x2),min(x3,x4));
m2=max(min(y1,y2),min(y3,y4));

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define closeio std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int maxn=10;
ll n,m,x1,y1,x2,y2,x3,y3,x4,y4;
int main()
{
int t;
cin>>t;
while(t--)
{
scanf("%I64d%I64d",&n,&m);
scanf("%I64d%I64d%I64d%I64d",&x1,&y1,&x2,&y2);
scanf("%I64d%I64d%I64d%I64d",&x3,&y3,&x4,&y4);
ll ans1 = 0, ans2 = 0;//ans1白色个数，ans2是黑色个数
if(n%2 == 1 && m%2 == 1)
{
ans1 = n*m/2+1;
ans2 = n*m/2;
}
else
{
ans1 = ans2 = n*m/2;
}

if((x1+y1)%2==0)//左下角为白色
{
ans2 -= (x2-x1+1)*(y2-y1+1)/2;
ans1 += (x2-x1+1)*(y2-y1+1)/2;
}
else//左下角为黑色
{
if((x2-x1+1)%2 == 1 && (y2-y1+1)%2 == 1)
{
ans2 -= ((x2-x1+1)*(y2-y1+1)/2+1);
ans1 += ((x2-x1+1)*(y2-y1+1)/2+1);
}
else
{
ans2 -= (x2-x1+1)*(y2-y1+1)/2;
ans1 += (x2-x1+1)*(y2-y1+1)/2;
}
}
if((x3+y3)%2==0)//左下角为白色
{
if((x4-x3+1)%2 == 1 && (y4-y3+1)%2 == 1)
{
ans2 += ((x4-x3+1)*(y4-y3+1)/2+1);
ans1 -= ((x4-x3+1)*(y4-y3+1)/2+1);
}
else
{
ans2 += (x4-x3+1)*(y4-y3+1)/2;
ans1 -= (x4-x3+1)*(y4-y3+1)/2;
}
}
else//左下角为黑色
{
ans2 += ((x4-x3+1)*(y4-y3+1)/2);
ans1 -= ((x4-x3+1)*(y4-y3+1)/2);
}
//处理相交
ll n1,n2,m1,m2;
n1=min(max(x1,x2),max(x3,x4));
m1=min(max(y1,y2),max(y3,y4));
n2=max(min(x1,x2),min(x3,x4));
m2=max(min(y1,y2),min(y3,y4));
if(n1>=n2&&m1>=m2)
{
swap(n1,n2);//这里需交换使后续计算为正值
swap(m1,m2);

if((n1+m1)%2==0)//左下角为白色
{
ans2 += (n2-n1+1)*(m2-m1+1)/2;
ans1 -= (n2-n1+1)*(m2-m1+1)/2;
}
else//左下角为黑色
{
if((n2-n1+1)%2 == 1 && (m2-m1+1)%2 == 1)
{
ans2 += ((n2-n1+1)*(m2-m1+1)/2+1);
ans1 -= ((n2-n1+1)*(m2-m1+1)/2+1);
}
else
{
ans2 += (n2-n1+1)*(m2-m1+1)/2;
ans1 -= (n2-n1+1)*(m2-m1+1)/2;
}
}
}
cout<<ans1<<' '<<ans2<<endl;
}
return 0;
}

• 还没有人评论，欢迎说说您的想法！

40935 0元 限免
28893 0元 限免