线段树经典解决问题poj1151，计算图形覆盖总面积。
1.用了半小时写了一个简单算法，看了看测试数据没过，原来理解题意错误。（如果提交就是WA）
2.然后又用了朴素的枚举，这次是TLE，看来是水平不行，要学习学习别人的思路了。
3.看完别人代码后，花了半天用自己的思路写了一遍，RTE。
4.原来是数组设小了，再次提交PE。
4.最后居然是要输出两个换行，晕倒!AC
线段树的应用还有很多，就此题来说基本的思维是用线段树的方法就每一块面积单独进行计算（按x轴分块），然后累加。此题由于是浮点型，还用到了离散化的方法来帮助线段树来进行转化。
最后show一下代码
1
#include "stdio.h"
2#include "stdlib.h"
3
4#define MAX 100
5
6struct node
7
{
8
int left;
9 int right;
10 double h;
11 double y2;
12
}xdtree[5 * MAX + 11];
13
14// xdtree_leaf_size = 2^(n - 1) = 200 < 256
15// n < 9
16// xdtree_size = 2^n - 1 = 511;
17struct axis
18{
19 double x1;
20 double y1;
21 double x2;
22 double y2;
23}area[MAX];
24
25double d[2 * MAX];
26
27void build_tree(int n, int l, int r)
28{
29 int m;
30
31 xdtree[n].left = l;
32 xdtree[n].right = r;
33 xdtree[n].h = 0;
34 xdtree[n].y2 = 0;
35
36 if (r - l == 1)
37 return;
38
39 m = (r + l) >> 1;
40
41 build_tree(2 * n + 1, l, m);
42 build_tree(2 * n + 2, m, r);
43}
44
45void insert(int i, double x1, double y1, double x2, double y2)
46{
47 int m;
48
49 if (xdtree[i].y2 >= y2)
50 return;
51
52 if (xdtree[i].right - xdtree[i].left == 1)
53
{
54
55 if (d[xdtree[i].left] == x1 && d[xdtree[i].right] == x2)
56 {
57 if (xdtree[i].y2 > y1)
58 {
59 xdtree[i].h += y2 - xdtree[i].y2;
60
}
61 else
62 {
63 xdtree[i].h += y2 - y1;
64 }
65 xdtree[i].y2 = y2;
66 }
67 }
68 else
69 {
70 m = (xdtree[i].left + xdtree[i].right) >> 1;
71
72 if (d[m] >= x2)
73 {
74 insert(2 * i + 1, x1, y1, x2, y2);
75 }
76 else if (d[m] <= x1)
77 {
78 insert(2 * i + 2, x1, y1, x2, y2);
79 }
80 else
81 {
82 insert(2 * i + 1, x1, y1, d[m], y2);
83 insert(2 * i + 2, d[m], y1, x2, y2);
84 }
85 }
86}
87
88double calc(int i)
89{
90 if (xdtree[i].right - xdtree[i].left == 1)
91 {
92 return xdtree[i].h * (d[xdtree[i].right] - d[xdtree[i].left]);
93 }
94 else
95 {
96 return calc(2 * i + 1) + calc(2 * i + 2);
97 }
98}
99
100
101int cmp_d(const double *p1, const double *p2)
102{
103 if (*p1 > *p2)
104 return 1;
105 else if (*p1 == *p2)
106 return 0;
107 else
108 return -1;
109}
110
111int cmp_y1(const struct axis *p1, const struct axis *p2)
112{
113 return cmp_d(&p1->y1, &p2->y1);
114}
115
116void main()
117{
118 int c, i, j, k, n;
119
120 n = 0;
121
122 while (scanf("%d", &c))
123 {
124 if (!c) break;
125
126 for (i = 0, k = 0; i < c; ++i)
127 {
128 scanf("%lf %lf %lf %lf", &area[i].x1, &area[i].y1, &area[i].x2, &area[i].y2);
129 d[k++] = area[i].x1;
130 d[k++] = area[i].x2;
131 }
132
133 qsort(d, k, sizeof(d[0]), cmp_d);
134
135 for (i = 1, j = 0; i < k; ++i)
136 {
137 if (d[j] != d[i])
138 {
139 d[++j] = d[i];
140 }
141 }
142
143 build_tree(0, 0, j);
144
145 qsort(area, c, sizeof(area[0]), cmp_y1);
146
147 for (i = 0; i < c; i++)
148 {
149 insert(0, area[i].x1, area[i].y1, area[i].x2, area[i].y2);
150 }
151 printf("Test case #%d\nTotal explored area: %0.2lf\n\n", ++n, calc(0));
152 }
153}
154
posted on 2010-08-15 23:38
margin 阅读(250)
评论(0) 编辑 收藏 引用