Picture【HDU - 1828】【扫描线】

103 阅读 0 评论 68 点赞

我是靠谱客的博主大力柜子，最近开发中收集的这篇文章主要介绍Picture【HDU - 1828】【扫描线】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

这道题求的是这些可能存在重叠的小方块可能构成的合成方块的周长的值是多少，有简单却会很复杂的做法就是去跑纵向和横向两次的扫描线，求得最后的两个周长和，但是这样的做法未免显得复杂了，我们完全可以只跑一次线段树（扫描线）来做到这样的要求。

思路：问题就是我们得去知道有多少个可以竖起来的边，也就是有在两条扫描线之间，有多少个独立的方块在其中？我们求得独立方块数，最后乘以2就是最后的竖的边的数量，那么在解决竖直边上的这个问题我们就首先解决了。接下去就是求解横向的边的长度，我们每次的扫描线，也就代表着目前处理到的线上有多长的区间，那么我们求一个与上一个状态的差值，就是目前没被覆盖的边的增加出来的周长了。于是，我们加起来就会得到最后的总的周长了。


1 #include <iostream>

2 #include <cstdio>

3 #include <cmath>

4 #include <string>

5 #include <cstring>

6 #include <algorithm>

7 #include <limits>

8 #include <vector>

9 #include <stack>
 10 #include <queue>
 11 #include <set>
 12 #include <map>
 13 #define lowbit(x) ( x&(-x) )
 14 #define pi 3.141592653589793
 15 #define e 2.718281828459045
 16 #define INF 0x3f3f3f3f
 17 #define HalF (l + r)>>1
 18 #define lsn rt<<1
 19 #define rsn rt<<1|1
 20 #define Lson lsn, l, mid
 21 #define Rson rsn, mid+1, r
 22 #define QL Lson, ql, qr
 23 #define QR Rson, ql, qr
 24 #define myself rt, l, r
 25 using namespace std;
 26 typedef unsigned long long ull;
 27 typedef long long ll;
 28 const int maxN = 1e4 + 7;
 29 int N, tot, X[maxN], _UP;
 30 struct node
 31 {
 32
int lx, rx, y, val;
 33
node(int a=0, int b=0, int c=0, int d=0):lx(a), rx(b), y(c), val(d) {}
 34 }line[maxN];
 35 bool cmp(node e1, node e2) { return e1.y < e2.y; }
 36 struct tree
 37 {
 38
int sum, siz, num;
 39
bool lc, rc;
 40
tree(int a=0, int b=0, int f=0, bool c=false, bool d=false):sum(a), siz(b), num(f), lc(c), rc(d) {}
 41
void clear() { sum = siz = num = 0; lc = rc = false; }
 42 }t[maxN<<2];
 43 inline void buildTree(int rt, int l, int r)
 44 {
 45 
t[rt].clear();
 46
if(l == r) return;
 47
int mid = HalF;
 48 
buildTree(Lson);
 49 
buildTree(Rson);
 50 }
 51 inline void pushup(int rt, int l, int r)
 52 {
 53
if(t[rt].siz)
 54 
{
 55
t[rt].sum = X[r + 1] - X[l];
 56
t[rt].lc = t[rt].rc = true;
 57
t[rt].num = 1;
 58 
}
 59
else if(l == r)
 60 
{
 61
t[rt].sum = t[rt].num = 0;
 62
t[rt].lc = t[rt].rc = false;
 63 
}
 64
else
 65 
{
 66
t[rt].sum = t[lsn].sum + t[rsn].sum;
 67
t[rt].lc = t[lsn].lc;
t[rt].rc = t[rsn].rc;
 68
t[rt].num = t[lsn].num + t[rsn].num - (t[lsn].rc && t[rsn].lc);
 69 
}
 70 }
 71 inline void update(int rt, int l, int r, int ql, int qr, int val)
 72 {
 73
if(ql <= l && qr >= r)
 74 
{
 75
t[rt].siz += val;
 76 
pushup(myself);
 77
return;
 78 
}
 79
int mid = HalF;
 80
if(qr <= mid) update(QL, val);
 81
else if(ql > mid) update(QR, val);
 82
else { update(QL, val); update(QR, val); }
 83 
pushup(myself);
 84 }
 85 inline void init()
 86 {
 87
tot = 0;
 88 }
 89 int main()
 90 {
 91
while(scanf("%d", &N) != EOF)
 92 
{
 93 
init();
 94
int lx, ly, rx, ry;
 95
for(int i=1; i<=N; i++)
 96 
{
 97
scanf("%d%d%d%d", &lx, &ly, &rx, &ry);
 98
line[++tot] = node(lx, rx, ly, 1);
 99
X[tot] = lx;
100
line[++tot] = node(lx, rx, ry, -1);
101
X[tot] = rx;
102 
}
103
sort(X + 1, X + tot + 1);
104
sort(line + 1, line + tot + 1, cmp);
105
_UP = (int)(unique(X + 1, X + tot + 1) - X - 1);
106
buildTree(1, 1, _UP);
107
int ans = 0, las = 0;
108
for(int i=1, l, r; i<tot; i++)
109 
{
110
l = (int)(lower_bound(X + 1, X + _UP + 1, line[i].lx) - X);
111
r = (int)(lower_bound(X + 1, X + _UP + 1, line[i].rx) - X - 1);
112
update(1, 1, _UP, l, r, line[i].val);
113
ans += abs(las - t[1].sum);
114
las = t[1].sum;
115
ans += (line[i + 1].y - line[i].y) * (t[1].num << 1);
116 
}
117
ans += line[tot].rx - line[tot].lx;
118
printf("%dn", ans);
119 
}
120
return 0;
121 }
122 /*
123 7
124 -15 0 5 10
125 -5 8 20 25
126 15 -4 24 14
127 0 -6 16 4
128 2 15 10 22
129 30 10 36 20
130 34 0 40 16
131 ans = 228
132 */