poj 1177 picture （扫描线）

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int y[100000];
int ln,n;
struct node
{
int l;
int r;
int ld,rd; //左右端点是否被覆盖,这里的左右是相对y轴的，也可以看成上下;
int line;
//线段树中flag连续为1的区域段数
int m;
//扫描线长度,线段树中flag为1的区域长度
int flag;
}cnt[10000000];
struct Line
{
int y1,y2;
int x;
int flag;
}l[1000000];
bool cmp(Line a,Line b)
{
if(a.x!=b.x)
return a.x<b.x;
return a.flag>b.flag;
}
void build(int l,int r,int index)
//建树初始化
{
cnt[index].flag=0;
cnt[index].l=l;
cnt[index].r=r;
cnt[index].ld=cnt[index].rd=cnt[index].line=cnt[index].m=0;
if(r-l==1)
return ;
int m=(l+r)/2;
build(l,m,index<<1);
build(m,r,index<<1|1);
}
void updata(int index)//更新m,line
{
if(cnt[index].flag>0)
{
cnt[index].m=y[cnt[index].r]-y[cnt[index].l];
cnt[index].line=cnt[index].ld=cnt[index].rd=1;
}
else if(cnt[index].r-cnt[index].l==1)
{
cnt[index].m=cnt[index].line=cnt[index].ld=cnt[index].rd=0;
}
else
{
cnt[index].m=cnt[index<<1].m+cnt[index<<1|1].m;
cnt[index].ld=cnt[index<<1].ld;
cnt[index].rd=cnt[index<<1|1].rd;
cnt[index].line=cnt[index<<1].line+cnt[index<<1|1].line-cnt[index<<1].rd*cnt[index<<1|1].ld;
}
}
void insert(int l,int r,int index,int flag) //插入竖线段,矩形左边的flag为1,右边的flag=-1
{
if(l<=y[cnt[index].l] && r>=y[cnt[index].r])
cnt[index].flag+=flag;
else if(cnt[index].r-cnt[index].l==1)
return ;
else
{
int md=(cnt[index].l+cnt[index].r)/2;
if(l>=y[md])
insert(l,r,index<<1|1,flag);
else if(r<=y[md])
insert(l,r,index<<1,flag);
else
{
insert(l,y[md],index<<1,flag);
insert(y[md],r,index<<1|1,flag);
}
}
updata(index);
}
int main()
{
while(~scanf("%d",&n))
{
ln=0;
for(int i=0;i<n;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
l[ln].y1=y1;
l[ln].y2=y2;
l[ln].x=x1;
l[ln].flag=1;
y[ln]=y1;
ln++;
l[ln].y1=y1;
l[ln].y2=y2;
l[ln].x=x2;
l[ln].flag=-1;
y[ln]=y2;
ln++;
}
sort(y,y+ln);
sort(l,l+ln,cmp);
int k=0;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

for(int i=0;i<ln;i++)//去重，离散化y
{
if(y[k]<y[i])
y[++k]=y[i];
}
build(0,k,1);
int ans=0;
int now_m=0,now_line=0;
for(int i=0;i<ln;i++)
{
insert(l[i].y1,l[i].y2,1,l[i].flag);
if(i!=0)
ans+=2*now_line*(l[i].x-l[i-1].x);
ans+=abs(cnt[1].m-now_m);
now_m=cnt[1].m;
now_line=cnt[1].line;
}
printf("%dn",ans);
}
return 0;
}