Hdu 1828(线段树+扫描线)

Hdu 1828
线段树扫描线求周长并,看这篇好文学习:
http://blog.csdn.net/tomorrowtodie/article/details/52048323

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXR = 10000 + 5;
const int MAXN = 5000 + 5;
const int Zinf = 100000;
struct xian
{
int l, r, h;
int f;
bool operator<(const xian &b) const
{
return h<b.h;
}
}a[MAXN*2];
int abss(int x) {return x<0 ? -x : x;}
int n;
#define lc (o*2)
#define rc (o*2+1)
#define M ((l+r)>>1)
struct st
{
int col[MAXR*4*4];//覆盖次数
int num[MAXR*4*4];//当前区间分离线段条数
int ls[MAXR*4*4], rs[MAXR*4*4];//左右结点是否被遮挡
int sum[MAXR*4*4];//计算时的有效区间长
void build(int o, int l ,int r)
{
col[o] = 0; num[o] = 0; ls[o] = rs[o] = 0; sum[o] = 0;
if (l==r) return ;
build(lc, l, M);
build(rc, M+1, r);
}
void pushup(int o, int l, int r)
{
if (col[o])
{
num[o] = 1;
ls[o] = rs[o] = 1;
sum[o] = r-l+1;
} else if (l==r)
{
num[o] = 0;
ls[o] = rs[o] = 0;
sum[o] = 0;
} else
{
ls[o] = ls[lc];
rs[o] = rs[rc];
sum[o] = sum[lc] + sum[rc];
num[o] = num[lc] + num[rc] - (rs[lc]&&ls[rc]);
}
}
void update(int o, int l, int r, int x, int y, int c)
{
if (x<=l&&r<=y)
{
col[o] += c;
pushup(o,l,r);
return ;
}
if (x<=M) update(lc, l, M, x, y, c);
if (M<y) update(rc, M+1, r, x, y, c);
pushup(o,l,r);
}
}tree;
int main()
{
while (scanf("%d", &n)==1)
{
int minr = Zinf, maxr = -Zinf;
for (int i=0;i<n;i++)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
minr = min(minr, min(x1,x2));
maxr = max(maxr, max(x1,x2));
a[i*2].l = a[i*2+1].l = x1;
a[i*2].r = a[i*2+1].r = x2;
a[i*2].h = y1; a[i*2+1].h = y2;
a[i*2].f = -1; a[i*2+1].f = 1;
}
sort(a, a+2*n);//数小,不用离散化。
tree.build(1, minr, maxr-1);
int last = 0;
int ans = 0;
for (int i=0;i<2*n;i++)
{
tree.update(1,minr,maxr-1,a[i].l, a[i].r-1, a[i].f);
ans += abss(tree.sum[1]-last);
ans += (a[i+1].h-a[i].h)*2*tree.num[1];
last = tree.sum[1];
}
printf("%d\n",ans);
}
return 0;
}

------ 本文结束 ------