Hdu 1542(线段树+扫描线)

Hdu 1542
线段树离散化以后进行扫描线。
http://www.cnblogs.com/scau20110726/archive/2013/03/21/2972808.html
这篇文章讲得很好,详解看以上网站

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXN = 100 + 5;
struct xian
{
int f; //up or down, up is -1, down is 1
double l, r;//the interval's end points
double h;//height
bool operator < (const xian &b) const
{
return h<b.h;
}
}a[MAXN*2];
double hashs[MAXN*2];//the hashsed points
int n;
#define lc o*2
#define rc o*2+1
#define M (l+r)/2
struct st
{
int col[MAXN*4*4];//col[i]>0 means this inerval was full marked
double sum[MAXN*4*4];//available room
void pushup(int o, int l, int r)
{
if (col[o]>0)
{
sum[o] = hashs[r+1]-hashs[l];
} else if (l==r) sum[o] = 0;
else {
sum[o] = sum[lc] + sum[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;
//binary-search the elements in hashs[]
int find(int x, int y, double v)
{
int l = x, r = y, mid;
while (l<r)
{
mid = (l+r)/2;
if (v>hashs[mid])
{
l = mid+1;
} else r = mid;
}
return r;
}
int main()
{
int kase = 0;
while (scanf("%d", &n)==1&&n)
{
kase++;
for (int i=0;i<n;i++)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1,&y1,&x2,&y2);
a[i*2].f = 1; a[i*2+1].f = -1;
a[i*2].l = x1; a[i*2+1].l = x1;
a[i*2].r = x2; a[i*2+1].r = x2;
a[i*2].h = y1; a[i*2+1].h = y2;//add xian
hashs[i*2] = x1; hashs[i*2+1] = x2;//add hashs
}
sort(hashs, hashs+2*n); sort(a, a+2*n); //sort to hashs
//delete the repeated elements
int m = 1;
for (int i=1;i<2*n;i++)
if (hashs[i]!=hashs[i-1]) hashs[m++] = hashs[i];
//produce
ms(tree.col, 0);
double ans = 0;
for (int i=0;i<n*2;i++)
{
int l = find(0, m, a[i].l);
int r = find(0, m, a[i].r)-1;
/*int l = lower_bound(hashs, hashs+m, a[i].l)-hashs;
int r = lower_bound(hashs, hashs+m, a[i].r)-hashs-1;*/
if (r>=l) tree.update(1,0,m-2,l,r,a[i].f);//一定要r>=l,这里原来错了
ans += (a[i+1].h-a[i].h)*tree.sum[1];
}
printf("Test case #%d\nTotal explored area: %.2f\n\n", kase, ans);
}
return 0;
}

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