/*3514. River Pollution
Accepted
2010 5 23
一道用线段树求矩形并的题目。
http://acm.tju.edu.cn/toj/showp.php?pid=3514
题目:受污染的河流会污染到它周围的村庄,给出河流的坐标求受污染的村庄的总数。
求矩形的并的方法:
将矩形的平行于y轴或者说平行于列的边,按照x从小到大排列。
然后求面积时,就分别求所到的边,与上一个边在y轴上覆盖了多长,用这个长度乘以
这两条边之间的x轴上的距离,搜索所有的边,就可以求的矩形并的面积。
在我们求在y轴上覆盖了多长的时候,可以用线段树来处理。当数据过大或不一定为整数时
还需要加上离散化。
ps:因为一小点错,错了一下午,刷了一片wrong answer。还好最后这个小问题还是被我给发现了。
坚持就是胜利啊。*/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
struct seg
{
int x,y1,y2;
int flag;
seg(){}
seg(int _x,int _y1,int _y2,int _f): x(_x),y1(_y1), y2(_y2), flag(_f){}
bool operator < ( const seg& a) const
{
return x < a.x;
}
}Edge[40005];
int f[600005];
int m[600005];
void update(int left,int right,int step)
{
if(left==right-1)
{
if(f[step]>0)
m[step]=1;
else
m[step]=0;
return ;
}
if(f[step]>0)
m[step]=right-left;
else
m[step]=m[2*step]+m[step*2+1];
}
void Buildtree(int left,int right,int l,int r,int c,int step)
{
if(left==right-1)
{
f[step]+=c;
update(left,right,step);
return ;
}
if(left==l&&right==r)
{
f[step]+=c;
update(left,right,step);
return ;
}
else
{
int mid=(left+right)>>1;
if(r<=mid)
Buildtree(left,mid,l,r,c,2*step);
else if(l>=mid)
Buildtree(mid,right,l,r,c,2*step+1);
else
{
Buildtree(left,mid,l,mid,c,2*step);
Buildtree(mid,right,mid,r,c,2*step+1);
}
update(left,right,step);
return ;
}
}
int main()
{
int t,n,x1,y1,x2,y2,i,j,my,pre;
long long ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(f,0,sizeof(f));
memset(m,0,sizeof(m));
j=my=0;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1==x2)
{
if(y1>y2) swap(y1,y2);
Edge[j++]=seg(x1-1,y1,y2,1);
Edge[j++]=seg(x1+1,y1,y2,-1);
}
else if(y1==y2)
{
if(x1>x2) swap(x1,x2);
Edge[j++]=seg(x1,y1-1,y1+1,1);
Edge[j++]=seg(x2,y1-1,y1+1,-1);
}
my=max(y2,my);
}
sort(Edge,Edge+j);
ans=0;
pre=Edge[0].x;
for(i=0;i<j;i++)
{
ans+=m[1]*(Edge[i].x-pre);
Buildtree(0,my+2,Edge[i].y1,Edge[i].y2,Edge[i].flag,1);
pre=Edge[i].x;
}
cout<<ans<<endl;
}
return 0;
}