線段樹(shù)經(jīng)典解決問(wèn)題poj1151，計(jì)算圖形覆蓋總面積。
1.用了半小時(shí)寫(xiě)了一個(gè)簡(jiǎn)單算法，看了看測(cè)試數(shù)據(jù)沒(méi)過(guò)，原來(lái)理解題意錯(cuò)誤。（如果提交就是WA）
2.然后又用了樸素的枚舉，這次是TLE，看來(lái)是水平不行，要學(xué)習(xí)學(xué)習(xí)別人的思路了。
3.看完別人代碼后，花了半天用自己的思路寫(xiě)了一遍，RTE。
4.原來(lái)是數(shù)組設(shè)小了，再次提交PE。
4.最后居然是要輸出兩個(gè)換行，暈倒!AC
線段樹(shù)的應(yīng)用還有很多，就此題來(lái)說(shuō)基本的思維是用線段樹(shù)的方法就每一塊面積單獨(dú)進(jìn)行計(jì)算（按x軸分塊），然后累加。此題由于是浮點(diǎn)型，還用到了離散化的方法來(lái)幫助線段樹(shù)來(lái)進(jìn)行轉(zhuǎn)化。
最后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 閱讀(264)
評(píng)論(0) 編輯 收藏 引用