poj1177

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<cmath>
#define L(x) (x<<1)
#define R(x) (x<<1 |1)
#define MAX 5010
using namespace std;
int cy[2*MAX];
int m1,m2;
class seg
{
public:
int x,y1,y2,f;
seg(){};
seg(int a,int b,int c,int d):x(a),y1(b),y2(c),f(d)
{}
bool operator< (const seg b)const
{
return x<b.x;
}
}line[MAX*2];
struct node
{
int l,r,length,cover;
int num;
int cr,cl;
}a[2*MAX];
void build(int t,int l,int r)
{
a[t].l=l;
a[t].r=r;
a[t].cover=0;
a[t].length=0;
a[t].cr=0;
a[t].cl=0;
a[t].num=0;
if(r-l==1)return ;
int mid=(l+r)/2;
build(L(t),l,mid);
build(R(t),mid,r);
}
int ll=0;
void uplen(int t)
{
if(a[t].cover>0)
{
a[t].length=cy[a[t].r]-cy[a[t].l];
a[t].num=1;
a[t].cr=1;
a[t].cl=1;
}
else
if(a[t].r-a[t].l==1)
{
a[t].length=0;
a[t].cr=0;
a[t].cl=0;
a[t].num=0;
}
else
{
a[t].cl=a[L(t)].cl;
a[t].cr=a[R(t)].cr;
a[t].num=a[L(t)].num+a[R(t)].num-a[L(t)].cr*a[R(t)].cl;
a[t].length=a[L(t)].length+a[R(t)].length;
}
}
void update(int t ,seg s)
{
if(cy[a[t].l]>=s.y1&&cy[a[t].r]<=s.y2)
{
a[t].cover+=s.f;
uplen(t);
return;
}
if(a[t].r-a[t].l==1)return ;
int mid=(a[t].l+a[t].r)/2;
if(s.y1<=cy[mid])
update(L(t),s);
if(s.y2>=cy[mid])
update(R(t),s);
uplen(t);
}
void addlen(int x1,int x2,int y1,int y2)
{
line[m1++]=seg(x1,y1,y2,1);
line[m1++]=seg(x2,y1,y2,-1);
cy[m2++]=y1;
cy[m2++]=y2;
}
int main()
{
int x1,x2,y1,y2;
int l1,l2;
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
m1=0;
m2=0;
ll=0;
l1=0;
l2=0;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
addlen(x1,x2,y1,y2);
}
sort(line,line+m1);
sort(cy,cy+m2);
m2=unique(cy,cy+m2)-cy;
build(1,0,m2-1);
for(i=0;i<m1;i++)
{
update(1,line[i]);
ll+=abs(a[1].length-l1);
if(i<m1-1)
{
ll+=2*a[1].num*(line[i+1].x-line[i].x);
}
l1=a[1].length;
}
printf("%dn",ll);
}
}