hdu 1828 Picture（矩形周长并）

78 阅读 0 评论 52 点赞

我是靠谱客的博主隐形萝莉，这篇文章主要介绍hdu 1828 Picture（矩形周长并），现在分享给大家，希望可以做个参考。

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1828
题目大意：就是给你n个矩形，每个矩形由左上和右上两个点确定，问你他们的周长并是多少？
思路：线段树+扫描线。同样需要左闭右开处理，稍微和面积并有点不同，底线的长度求法和面积并一样，关键是还要-上次的底线长度，求这个值abs，然后这就是
update当前这条line之后新增的横的长度。然后就是求竖的那种线有几根的问题，如果某个区间被某几条线完全覆盖，那么我们就设它的
竖线有两根，然后在定义两个数组 lbd，rbd，表示这个区间的左右端点存不存在竖线（因为是左闭右开，右端点是-1的，其实是l、r+1 存不存在竖线），
push_up的时候，如果左儿子的rbd存在，右儿子的lbd存在，就要两个numseg值加起来-2，因为这两条线重合了。具体的可以看代码里的 push_up，我感觉
那里是关键。
代码是直接从面积那里并改过来的。

代码如下：

复制代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int MAXN = 5005<<1;
struct Line
{
int l,r,h;
int flag;
Line(){}
Line(int a,int b,int c,int d)
{
l = a;
r = b;
h = c;
flag = d;
}
bool operator < (const Line &tmp) const
{
return h < tmp.h;
}
} line[MAXN];
int x[MAXN];
int Bin(int l,int r,int key)
{
while(l <= r)
{
int mid = (l+r)>>1;
if(x[mid] == key)
{
return mid;
}
else if(x[mid] < key)
l = mid+1;
else r = mid-1;
}
return -1;
}
int sum[MAXN<<2],cnt[MAXN<<2],numseg[MAXN<<2],lbd[MAXN<<2],rbd[MAXN<<2];
void push_up(int rt,int l,int r)
{
if(cnt[rt])
{
sum[rt] = x[r+1]-x[l];
numseg[rt] = 2;
lbd[rt] = rbd[rt] = 1;
}
else if(l == r) sum[rt] = numseg[rt] = lbd[rt] = rbd[rt] = 0;
else
{
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
numseg[rt] = numseg[rt<<1]+numseg[rt<<1|1];
if(lbd[rt<<1|1] && rbd[rt<<1]) numseg[rt] -= 2;
lbd[rt] = lbd[rt<<1];
rbd[rt] = rbd[rt<<1|1];
}
}
void update(int rt,int l,int r,int a,int b,int c)
{
if(a <= l && b >= r)
{
cnt[rt] += c;
push_up(rt,l,r);
return ;
}
int mid = l+r>>1;
if(a <= mid) update(lson,a,b,c);
if(b > mid) update(rson,a,b,c);
push_up(rt,l,r);
}
void build(int rt,int l,int r)
{
cnt[rt] = sum[rt] = numseg[rt] = lbd[rt] = rbd[rt] = 0;
if(l == r)
return ;
int mid = l+r>>1;
build(lson);
build(rson);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int a,b,c,d;
int tot = 0;
for(int i = 0;i < n;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
x[tot] = a;
line[tot++] = Line(a,c,b,1);
x[tot] = c;
line[tot++] = Line(a,c,d,-1);
}
sort(x,x+tot);
sort(line,line+tot);
int m = unique(x,x+tot)-x;
build(1,0,m-1);
int ans = 0;
int last = 0;
for(int i = 0;i < tot;i++)
{
int l = Bin(0,m-1,line[i].l);
int r = Bin(0,m-1,line[i].r);
if(l >= r) continue;
//printf("l = %d,r = %d,m = %dn",l,r,m);
update(1,0,m-1,l,r-1,line[i].flag);
ans += numseg[1]*(i == tot-1 ? 0 : (line[i+1].h-line[i].h));
ans += abs(sum[1]-last);
last = sum[1];
//printf("%d,%d,ans = %dn",numseg[1],sum[1],ans);
}
printf("%dn",ans);
}
return 0;
}
/*
2
10 10 20 20
15 15 25 25
*/

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int MAXN = 5005<<1;
struct Line
{
int l,r,h;
int flag;
Line(){}
Line(int a,int b,int c,int d)
{
l = a;
r = b;
h = c;
flag = d;
}
bool operator < (const Line &tmp) const
{
return h < tmp.h;
}
} line[MAXN];
int x[MAXN];
int Bin(int l,int r,int key)
{
while(l <= r)
{
int mid = (l+r)>>1;
if(x[mid] == key)
{
return mid;
}
else if(x[mid] < key)
l = mid+1;
else r = mid-1;
}
return -1;
}
int sum[MAXN<<2],cnt[MAXN<<2],numseg[MAXN<<2],lbd[MAXN<<2],rbd[MAXN<<2];
void push_up(int rt,int l,int r)
{
if(cnt[rt])
{
sum[rt] = x[r+1]-x[l];
numseg[rt] = 2;
lbd[rt] = rbd[rt] = 1;
}
else if(l == r) sum[rt] = numseg[rt] = lbd[rt] = rbd[rt] = 0;
else
{
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
numseg[rt] = numseg[rt<<1]+numseg[rt<<1|1];
if(lbd[rt<<1|1] && rbd[rt<<1]) numseg[rt] -= 2;
lbd[rt] = lbd[rt<<1];
rbd[rt] = rbd[rt<<1|1];
}
}
void update(int rt,int l,int r,int a,int b,int c)
{
if(a <= l && b >= r)
{
cnt[rt] += c;
push_up(rt,l,r);
return ;
}
int mid = l+r>>1;
if(a <= mid) update(lson,a,b,c);
if(b > mid) update(rson,a,b,c);
push_up(rt,l,r);
}
void build(int rt,int l,int r)
{
cnt[rt] = sum[rt] = numseg[rt] = lbd[rt] = rbd[rt] = 0;
if(l == r)
return ;
int mid = l+r>>1;
build(lson);
build(rson);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int a,b,c,d;
int tot = 0;
for(int i = 0;i < n;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
x[tot] = a;
line[tot++] = Line(a,c,b,1);
x[tot] = c;
line[tot++] = Line(a,c,d,-1);
}
sort(x,x+tot);
sort(line,line+tot);
int m = unique(x,x+tot)-x;
build(1,0,m-1);
int ans = 0;
int last = 0;
for(int i = 0;i < tot;i++)
{
int l = Bin(0,m-1,line[i].l);
int r = Bin(0,m-1,line[i].r);
if(l >= r) continue;
//printf("l = %d,r = %d,m = %dn",l,r,m);
update(1,0,m-1,l,r-1,line[i].flag);
ans += numseg[1]*(i == tot-1 ? 0 : (line[i+1].h-line[i].h));
ans += abs(sum[1]-last);
last = sum[1];
//printf("%d,%d,ans = %dn",numseg[1],sum[1],ans);
}
printf("%dn",ans);
}
return 0;
}
/*
2
10 10 20 20
15 15 25 25
*/