18.10.22 POJ 1177 Picture（线段树+离散化+二分）

57 阅读 0 评论 38 点赞

我是靠谱客的博主靓丽老虎，最近开发中收集的这篇文章主要介绍18.10.22 POJ 1177 Picture（线段树+离散化+二分），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

描述

A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter.

Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1.

The corresponding boundary is the whole set of line segments drawn in Figure 2.

The vertices of all rectangles have integer coordinates.输入Your program is to read from standard input. The first line contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.

0 <= number of rectangles < 5000
All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area.输出Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles.样例输入

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

样例输出

来源

IOI 1998


1 #include <iostream>

2 #include <string.h>

3 #include <algorithm>

4 #include <stack>

5 #include <string>

6 #include <math.h>

7 #include <queue>

8 #include <stdio.h>

9 #include <string.h>
 10 #include <vector>
 11 #include <fstream>
 12 #include <set>
 13 #include<map>
 14 #define l(rt) rt*2
 15 #define r(rt) rt*2+1
 16 #define mid(l,r) (l+r)/2
 17
 18 using namespace std;
 19
 20 const int maxn = 5005;
 21 struct node {
 22
int l, r;
 23
int len;//本区间有多长被矩形覆盖
 24
int block;
 25
bool cl, cr;
 26
int cover;
 27 }tree[maxn*8];
 28 struct cline {
 29
int x, y1, y2;
 30
bool left;
 31
bool operator <(cline a) {
 32
if (x == a.x)
 33
return left > a.left;
 34
return x < a.x;
 35 
}
 36 }line[maxn*2];
 37 int n,col[maxn*2];
 38
 39 void build(int rt, int l, int r) {
 40
tree[rt].l = l, tree[rt].r = r;
 41
tree[rt].cover = 0,tree[rt].len=0;
 42
tree[rt].block = 0, tree[rt].cl = tree[rt].cr = false;
 43
if (l == r)return;
 44
build(r(rt), mid(l, r) + 1, r);
 45 
build(l(rt), l, mid(l, r));
 46 }
 47
 48 void insert(int rt, int l, int r) {
 49
if (tree[rt].l == l && tree[rt].r == r) {
 50
tree[rt].cover++;
 51
tree[rt].len = col[r + 1] - col[l];
 52
tree[rt].block = 1, tree[rt].cl = tree[rt].cr = true;
 53
return;
 54 
}
 55
int midn = mid(tree[rt].l, tree[rt].r);
 56
if (l > midn)
 57 
insert(r(rt), l, r);
 58
else if (r <= midn)
 59 
insert(l(rt), l, r);
 60
else {
 61 
insert(l(rt), l, midn);
 62
insert(r(rt), midn + 1, r);
 63 
}
 64
if (tree[rt].cover == 0)
 65 
{
 66
tree[rt].len = tree[l(rt)].len + tree[r(rt)].len;
 67
tree[rt].cl = tree[l(rt)].cl;
 68
tree[rt].cr = tree[r(rt)].cr;
 69
tree[rt].block = tree[l(rt)].block + tree[r(rt)].block - tree[l(rt)].cr*tree[r(rt)].cl;
 70 
}
 71
return;
 72 }
 73
 74 void Delete(int rt, int l, int r) {
 75
if (tree[rt].l == l && tree[rt].r == r) {
 76
tree[rt].cover--;
 77
if (tree[rt].cover == 0) {
 78
if (l == r)
 79 
{
 80
tree[rt].len = 0;
 81
tree[rt].block = 0;
 82
tree[rt].cl = tree[rt].cr = false;
 83 
}
 84
else
 85 
{
 86
tree[rt].len = tree[l(rt)].len + tree[r(rt)].len;
 87
tree[rt].cl = tree[l(rt)].cl;
 88
tree[rt].cr = tree[r(rt)].cr;
 89
tree[rt].block = tree[l(rt)].block + tree[r(rt)].block - tree[l(rt)].cr*tree[r(rt)].cl;
 90 
}
 91 
}
 92
return;
 93 
}
 94
int midn = mid(tree[rt].l, tree[rt].r);
 95
if (l > midn)
 96 
Delete(r(rt), l, r);
 97
else if (r <= midn)
 98 
Delete(l(rt), l, r);
 99
else
100
Delete(l(rt), l, midn), Delete(r(rt), midn + 1, r);
101
if (tree[rt].cover == 0)
102 
{
103
tree[rt].len = tree[l(rt)].len + tree[r(rt)].len;
104
tree[rt].cl = tree[l(rt)].cl;
105
tree[rt].cr = tree[r(rt)].cr;
106
tree[rt].block = tree[l(rt)].block + tree[r(rt)].block - tree[l(rt)].cr*tree[r(rt)].cl;
107 
}
108
return;
109 }
110
111 int binary_find(int s, int e, int val) {
112
while (s < e) {
113
int x = s + (e - s) / 2;
114
if (col[x] >= val)e = x;
115
else s = x + 1;
116 
}
117
return s;
118 }
119
120 void init() {
121
scanf("%d", &n);
122
int yc, lc;
123
yc=lc = 0;
124
for (int i = 1; i <= n; i++) {
125
int x1, x2, y1, y2;
126
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
127
col[++yc] = y1, col[++yc] = y2;;
128
line[++lc].x = x1, line[lc].y1 = y1, line[lc].y2 = y2, line[lc].left = true;
129
line[++lc].x = x2, line[lc].y1 = y1, line[lc].y2 = y2, line[lc].left = false;
130 
}
131
sort(col + 1, col + yc+1);
132
yc = unique(col + 1, col + yc + 1) - col - 1;//横线yc条
133
sort(line + 1, line + 1 + lc);
134
build(1, 1, yc - 1);
135
int prec = 0,nowc,ans=0;
136
for (int i = 1; i <= lc; i++) {
137
int l = binary_find(1, yc+1, line[i].y1);
138
int r = binary_find(1, yc+1, line[i].y2)-1;
139
if (line[i].left)insert(1, l, r);
140
else Delete(1, l, r);
141
nowc=tree[1].len;
142
ans += abs(nowc - prec);
143
if(i!=lc)
144
ans+=(tree[1].block * 2 * (line[i + 1].x - line[i].x));
145
prec = nowc;
146 
}
147
printf("%dn", ans);
148 }
149
150 int main()
151 {
152 
init();
153
return 0;
154 }