線段樹經典解決問題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 閱讀(271)
評論(0) 編輯 收藏 引用