HDU - 1828 Picture （线段树求并周长）

90 阅读 0 评论 60 点赞

我是靠谱客的博主善良大碗，这篇文章主要介绍HDU - 1828 Picture （线段树求并周长），现在分享给大家，希望可以做个参考。

题意：求出组合的图形的外围轮廓的长

思路：相比于并面积的区别在于多了几个标记变量，参考数据结构的选择与算法效率，难懂的是ans的作用，引用一句：

好像区间[0,10]，被[1,2],[4,5]覆盖，那么num=2

好像区间[0,10],被[1,3][4,5]覆盖，那么num=1，因为他们刚好连在一起了

好像区间[0,10],被[1,5][2,6]覆盖，那么num=1，因为还是连起来的一段

前面的工作是相同的，把横线保存在一个表中，按竖直位置排序，然后从下往上扫描所有横线，在这个方法中，每次扫描一条横线，都能计算出两不部分值，一部分是横线的，一部分是竖线的

而计算横线部分的方法和第一种方法是一样的，即求出【现在这次总区间被覆盖的长度和上一次总区间被覆盖的长度的差的绝对值】，另外怎么算竖线部分呢?首先我们要知道添加了这条横线后会有多少条竖线，答案是2*num，所以为什么要记录num呢，因为总区间被num条线段覆盖，那么必定有2*num的端点，这些端点其实就是连着竖线，那么这些竖线的长度是多少呢？

就是【下一条横线的高度-现在这条横线的高度】，只要把这个高度乘上2*num即可

复制代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 10200;
int ym[MAXN];
struct Tree{
int li,ri,lb,rb;
int lenth,ans,cover;
}s[50000];
struct node{
int x,y1,y2;
int flag;
}t[50000];
int cmp(node st, node sd){
if (st.x != sd.x)
return st.x < sd.x;
return st.flag > sd.flag;
}
void len(int num){
if (s[num].cover > 0)
s[num].lenth = s[num].ri - s[num].li;
else s[num].lenth = s[num+num].lenth + s[num+num+1].lenth;
}
void slen(int num){
if (s[num].cover > 0)
s[num].ans = 1;
else {
s[num].ans = s[num+num].ans + s[num+num+1].ans;
if (s[num+num].rb != 0 && s[num+num+1].lb != 0)
s[num].ans--;
}
}
void build(int x, int y, int num){
s[num].li = ym[x];
s[num].ri = ym[y];
s[num].lenth = 0;
s[num].cover = s[num].rb = s[num].lb = s[num].ans = 0;
if (x + 1 == y)
return;
int mid = (x+y)>>1;
build(x,mid,num*2);
build(mid,y,num*2+1);
}
void modify(int num, node st){
if (st.y1 == s[num].li)
s[num].lb += st.flag;
if (st.y2 == s[num].ri)
s[num].rb += st.flag;
if (st.y1 == s[num].li && st.y2 == s[num].ri)
s[num].cover += st.flag;
else {
if (st.y1 >= s[num*2].ri)
modify(num*2+1,st);
else if (st.y2 <= s[num*2+1].li)
modify(num*2,st);
else {
node sd = st;
sd.y2 = s[num*2].ri;
modify(num*2,sd);
sd = st;
sd.y1 = s[num*2+1].li;
modify(num*2+1,sd);
}
}
len(num);
slen(num);
}
int main(){
int n;
int x1,y1,x2,y2;
int sum = 0;
while (scanf("%d",&n) != EOF){
sum = 0;
int cnt = 1;
for (int i = 1; i <= n; i++){
scanf("%d%d%d%d",&x1, &y1, &x2, &y2);
ym[cnt] = y1;
t[cnt].x = x1;
t[cnt].y1 = y1;
t[cnt].y2 = y2;
t[cnt++].flag = 1;
ym[cnt] = y2;
t[cnt].x = x2;
t[cnt].y1 = y1;
t[cnt].y2 = y2;
t[cnt++].flag = -1;
}
sort(ym+1,ym+cnt);
sort(t+1,t+cnt,cmp);
build(1,cnt-1,1);
int lastn = 0,lasts = 0;
for (int i = 1; i < cnt; i++){
modify(1,t[i]);
sum += abs(lasts-s[1].lenth);
if (i != 1)
sum += lastn*(t[i].x - t[i-1].x)*2;
lastn = s[1].ans;
lasts = s[1].lenth;
}
cout << sum << endl;
}
return 0;
}

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 10200;
int ym[MAXN];
struct Tree{
int li,ri,lb,rb;
int lenth,ans,cover;
}s[50000];
struct node{
int x,y1,y2;
int flag;
}t[50000];
int cmp(node st, node sd){
if (st.x != sd.x)
return st.x < sd.x;
return st.flag > sd.flag;
}
void len(int num){
if (s[num].cover > 0)
s[num].lenth = s[num].ri - s[num].li;
else s[num].lenth = s[num+num].lenth + s[num+num+1].lenth;
}
void slen(int num){
if (s[num].cover > 0)
s[num].ans = 1;
else {
s[num].ans = s[num+num].ans + s[num+num+1].ans;
if (s[num+num].rb != 0 && s[num+num+1].lb != 0)
s[num].ans--;
}
}
void build(int x, int y, int num){
s[num].li = ym[x];
s[num].ri = ym[y];
s[num].lenth = 0;
s[num].cover = s[num].rb = s[num].lb = s[num].ans = 0;
if (x + 1 == y)
return;
int mid = (x+y)>>1;
build(x,mid,num*2);
build(mid,y,num*2+1);
}
void modify(int num, node st){
if (st.y1 == s[num].li)
s[num].lb += st.flag;
if (st.y2 == s[num].ri)
s[num].rb += st.flag;
if (st.y1 == s[num].li && st.y2 == s[num].ri)
s[num].cover += st.flag;
else {
if (st.y1 >= s[num*2].ri)
modify(num*2+1,st);
else if (st.y2 <= s[num*2+1].li)
modify(num*2,st);
else {
node sd = st;
sd.y2 = s[num*2].ri;
modify(num*2,sd);
sd = st;
sd.y1 = s[num*2+1].li;
modify(num*2+1,sd);
}
}
len(num);
slen(num);
}
int main(){
int n;
int x1,y1,x2,y2;
int sum = 0;
while (scanf("%d",&n) != EOF){
sum = 0;
int cnt = 1;
for (int i = 1; i <= n; i++){
scanf("%d%d%d%d",&x1, &y1, &x2, &y2);
ym[cnt] = y1;
t[cnt].x = x1;
t[cnt].y1 = y1;
t[cnt].y2 = y2;
t[cnt++].flag = 1;
ym[cnt] = y2;
t[cnt].x = x2;
t[cnt].y1 = y1;
t[cnt].y2 = y2;
t[cnt++].flag = -1;
}
sort(ym+1,ym+cnt);
sort(t+1,t+cnt,cmp);
build(1,cnt-1,1);
int lastn = 0,lasts = 0;
for (int i = 1; i < cnt; i++){
modify(1,t[i]);
sum += abs(lasts-s[1].lenth);
if (i != 1)
sum += lastn*(t[i].x - t[i-1].x)*2;
lastn = s[1].ans;
lasts = s[1].lenth;
}
cout << sum << endl;
}
return 0;
}