|
#include<stdio.h>
#include<algorithm>
using namespace std;
const int Maxn=5000;
struct rectangle
{
int x1,x2,y1,y2;
}rec[Maxn];
int horizontal[Maxn*2],vertical[Maxn*2],record[Maxn*2];
int n;
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int lookup(int s[],int key)
{
int begin=0,end=2*n-1,middle;
while(begin<=end)
{
middle=(begin+end)/2;
if(s[middle]==key)
return middle;
else if(s[middle]>key)
end=middle-1;
else
begin=middle+1;
}
}
int count_x(int x1,int x2)
{
int i;
for(i=0;i<n;i++)
{
if(x1>=rec[i].x1&&x2<=rec[i].x2) //该矩形横跨了该组超元线段
{
record[lookup(vertical,rec[i].y2)]++;
record[lookup(vertical,rec[i].y1)]--;
}
}
int sum=0,add=0;
for(i=0;i<2*n;i++)
{
if(record[i]!=0)
{
if(add==0)
sum++;
add+=record[i];
if(add==0)
sum++;
}
}
return sum;
}
int count_y(int y1,int y2)
{
int i;
for(i=0;i<n;i++)
{
if(rec[i].y1<=y1&&rec[i].y2>=y2)
{
record[lookup(horizontal,rec[i].x2)]++;
record[lookup(horizontal,rec[i].x1)]--;
}
}
int sum=0,add=0;
for(i=0;i<2*n;i++)
{
if(record[i]!=0)
{
if(add==0)
sum++;
add+=record[i];
if(add==0)
sum++;
}
}
return sum;
}
int main()
{
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&rec[i].x1,&rec[i].y1,&rec[i].x2,&rec[i].y2);
horizontal[i*2]=rec[i].x1;horizontal[i*2+1]=rec[i].x2;
vertical[i*2]=rec[i].y1;vertical[i*2+1]=rec[i].y2;
}
qsort(horizontal,n*2,sizeof(int),cmp);
qsort(vertical,n*2,sizeof(int),cmp);
int length,amount,perimeter=0;
for(i=0;i<n*2-1;i++)
{
length=horizontal[i+1]-horizontal[i];
if(length!=0)
{
memset(record,0,sizeof(record)); ///记录矩形的上下两边横跨超元线段的情况
amount=count_x(horizontal[i],horizontal[i+1]);
perimeter+=length*amount;
}
}
for(i=0;i<n*2-1;i++)
{
length=vertical[i+1]-vertical[i];
if(length!=0)
{
memset(record,0,sizeof(record)); ///记录矩形的左右两边横跨超元线段的情况
amount=count_y(vertical[i],vertical[i+1]);
perimeter+=length*amount;
}
}
printf("%d\n",perimeter);
return 0;
}
|
