2019计蒜之道初赛4 B. 腾讯益智小游戏—矩形面积交（简单）（矩形交集）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

B. 腾讯益智小游戏—矩形面积交（简单）

1000ms
262144K

腾讯游戏开发了一款全新的编程类益智小游戏，最新推出的一个小游戏题目是关于矩形面积交的。聪明的你能解出来吗？看下面的题目接招吧。

给定二维平面上 nn 个与坐标轴平行的矩形，每个矩形是形如 \lbrace (x,y) | x,y \in R, x_1 \le x \le x_2, y_1 \le y \le y_2 \rbrace{(x,y)∣x,y∈R,x1≤x≤x2,y1≤y≤y2} 的点集，你的任务是对于每个矩形，计算它与其他矩形的交集。

具体来说，令 area(i,j)area(i,j) 表示第 ii 个矩形与第 jj 个矩形的交集面积，你需要对于 i = 1, 2, \cdots, ni=1,2,⋯,n，计算 \displaystyle\sum_{1 \le j \le n, i \neq j, area(i,j)>0} 11≤j≤n,i=j,area(i,j)>0∑1 和 \displaystyle\sum_{1 \le j \le n,i \neq j} area(i,j)1≤j≤n,i=j∑area(i,j) 的值。

输入格式

输入包含多组测试数据，输入的第一行包含一个正整数 TT，表示测试数据的组数。

接下来依次描述每组测试数据，对于每组测试数据:

第一行包含一个正整数 nn，表示矩形的数量。

接下来 nn 行，每行包含四个非负整数 x_1, y_1, x_2x1,y1,x2 和 y_2y2，表示一个矩形 \lbrace (x,y) | x,y \in R, x_1 \le x \le x_2, y_1 \le y \le y_2 \rbrace{(x,y)∣x,y∈R,x1≤x≤x2,y1≤y≤y2}，保证有 x_1 < x_2x1<x2 和 y_1 < y_2y1<y2。

输出格式

对于每组测试数据，输出 nn 行，其中第 ii 行包含两个非负整数，用恰好一个空格隔开，这里第 ii 行的第一个整数表示与输入给出的第 ii 个矩形严格有交集的矩形数量（不含第 ii 个矩形），第二个整数表示这些矩形分别与第 ii 个矩形的交集面积之和。

数据范围

所有测试数据的 nn 之和不超过 50005000，且坐标均为不超过 50005000 的非负整数。

样例输入复制

2
2
0 0 1 1
1 1 2 2
3
0 0 2 6
1 1 4 4
1 3 3 9

样例输出复制

0 0
0 0
2 6
2 5
2 5矩形交集。
给出坐标点，求矩形交集个数与单位面积。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;struct Node{
int x1,y1,x2,y2;
}a[];int calc(int a1x1,int a1y1,int a1x2,int a1y2,int a2x1,int a2y1,int a2x2,int a2y2){
int c=;
ll m1=max(min(a1x1,a1x2),min(a2x1,a2x2));
ll n1=max(min(a1y1,a1y2),min(a2y1,a2y2));
ll m2=min(max(a1x1,a1x2),max(a2x1,a2x2));
ll n2=min(max(a1y1,a1y2),max(a2y1,a2y2));
if(m2>m1&&n2>n1) return ;
return ;
}
ll cals(int a1x1,int a1y1,int a1x2,int a1y2,int a2x1,int a2y1,int a2x2,int a2y2){
int c=;
ll m1=max(min(a1x1,a1x2),min(a2x1,a2x2));
ll n1=max(min(a1y1,a1y2),min(a2y1,a2y2));
ll m2=min(max(a1x1,a1x2),max(a2x1,a2x2));
ll n2=min(max(a1y1,a1y2),max(a2y1,a2y2));
if(m2>m1&&n2>n1) return (m2-m1)*(n2-n1);
return ;
}
int main()
{
int t,n,i,j;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=;i<=n;i++){
scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
}
for(i=;i<=n;i++){
int c=;
ll s=;
for(j=;j<=n;j++){
if(i==j) continue;
c+=calc(a[i].x1,a[i].y1,a[i].x2,a[i].y2,a[j].x1,a[j].y1,a[j].x2,a[j].y2);
s+=cals(a[i].x1,a[i].y1,a[i].x2,a[i].y2,a[j].x1,a[j].y1,a[j].x2,a[j].y2);
}
printf("%d %lld\n",c,s);
}
}
return ;
}