当前位置：首页 > news >正文

poj 1151 Atlantis(离散+线段树)

news 来源：原创 2024/5/5 13:38:06

http://poj.org/problem?id=1151

　　数据量比较小，不过也是可以先离散坐标，再构建线段树，然后用扫描线在每个关键位置插入/删除线段并进行面积相加。

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <map>
  5 #include <vector>
  6 
  7 using namespace std;
  8 
  9 map<double, int> id;
 10 vector<double> x;
 11 struct Rect {
 12     double x1, x2, y;
 13     bool end;
 14 } ;
 15 vector<Rect> rect;
 16 const int maxn = 300;
 17 double sum[maxn << 2];
 18 int late[maxn << 2], mx[maxn << 2], mn[maxn << 2];
 19 
 20 bool cmp(const Rect a, const Rect b) {
 21     return a.y < b.y;
 22 }
 23 
 24 void input(int n) {
 25     double x1, y1, x2, y2;
 26     Rect tmp;
 27 
 28     rect.clear();
 29     x.clear();
 30     id.clear();
 31     for (int i = 0; i < n; i++) {
 32         scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
 33         if (x1 > x2) swap(x1, x2);
 34         if (y1 > y2) swap(y1, y2);
 35         tmp.x1 = x1, tmp.x2 = x2, tmp.y = y1, tmp.end = false;
 36         rect.push_back(tmp);
 37         tmp.y = y2, tmp.end = true;
 38         rect.push_back(tmp);
 39         x.push_back(x1);
 40         x.push_back(x2);
 41     }
 42 //    for (int i = 0, endi = x.size(); i < endi; i++) {
 43 //        printf("%.3f\n", x[i]);
 44 //    }
 45     sort(x.begin(), x.end());
 46     sort(rect.begin(), rect.end(), cmp);
 47     x.end() = unique(x.begin(), x.end());
 48 
 49     for (int i = 0, endi = x.size(); i < endi; i++) {
 50         id[x[i]] = i;
 51     }
 52 
 53 //    for (int i = 0, endi = x.size(); i < endi; i++) {
 54 //        printf("%.3f %d\n", x[i], id[x[i]]);
 55 //    }
 56 }
 57 
 58 #define lson l, m, rt << 1
 59 #define rson m, r, rt << 1 | 1
 60 
 61 void up(int rt) {
 62     int ls = rt << 1, rs = rt << 1 | 1;
 63 
 64     mn[rt] = min(mn[ls], mn[rs]);
 65     mx[rt] = max(mx[ls], mx[rs]);
 66     sum[rt] = sum[ls] + sum[rs];
 67 }
 68 
 69 void down(int rt, int l, int r) {
 70     if (late[rt]) {
 71         int ls = rt << 1, rs = rt << 1 | 1;
 72         int m = (l + r) >> 1;
 73 
 74         mx[ls] += late[rt];
 75         mn[ls] += late[rt];
 76         if (mn[ls]) {
 77             sum[ls] = x[m] - x[l];
 78         }
 79         if (!mx[ls]) {
 80             sum[ls] = 0.0;
 81         }
 82         mx[rs] += late[rt];
 83         mn[rs] += late[rt];
 84         if (mn[rs]) {
 85             sum[rs] = x[r] - x[m];
 86         }
 87         if (!mx[rs]) {
 88             sum[rs] = 0.0;
 89         }
 90         late[ls] += late[rt];
 91         late[rs] += late[rt];
 92         late[rt] = 0;
 93     }
 94 }
 95 
 96 void build(int l, int r, int rt) {
 97     sum[rt] = 0.0;
 98     mx[rt] = mn[rt] = late[rt] = 0;
 99     if (r - l == 1) {
100         return ;
101     }
102     int m = (l + r) >> 1;
103 
104     build(lson);
105     build(rson);
106 }
107 
108 void fix(int l, int r, int rt) {
109     if (r - l == 1 || mn[rt] || mn[rt] == mx[rt]) {
110         if (!mx[rt]) sum[rt] = 0.0;
111         if (mn[rt]) sum[rt] = x[r] - x[l];
112         return ;
113     }
114     int m = (l + r) >> 1;
115 
116     down(rt, l, r);
117     fix(lson);
118     fix(rson);
119     up(rt);
120 }
121 
122 void update(int L, int R, int k, int l, int r, int rt) {
123 //    printf("%d %d\n", l, r);
124     if (L <= l && r <= R) {
125         mn[rt] += k;
126         mx[rt] += k;
127         late[rt] += k;
128         if (mn[rt]) sum[rt] = x[r] - x[l];
129         if (!mx[rt]) sum[rt] = 0.0;
130         if (!mn[rt] && mx[rt]) fix(l, r, rt);
131 
132         return ;
133     }
134     int m = (l + r) >> 1;
135 
136     down(rt, l, r);
137     if (L < m) update(L, R, k, lson);
138     if (m < R) update(L, R, k, rson);
139     up(rt);
140 }
141 
142 double deal(int n) {
143     double ret = 0.0;
144 
145     update(id[rect[0].x1], id[rect[0].x2], 1, 0, x.size(), 1);
146     for (int i = 1, endi = rect.size(); i < endi; i++) {
147         ret += sum[1] * (rect[i].y - rect[i - 1].y);
148 //        printf("%.2f %.2f\n", ret, sum[1]);
149 //        printf("%d %d\n", id[rect[i].x1], id[rect[i].x2]);
150 //        printf("%d\n", x.size());
151         if (rect[i].end) {
152             update(id[rect[i].x1], id[rect[i].x2], -1, 0, x.size(), 1);
153         } else {
154             update(id[rect[i].x1], id[rect[i].x2], 1, 0, x.size(), 1);
155         }
156     }
157 
158     return ret;
159 }
160 
161 int main() {
162 //    freopen("in", "r", stdin);
163     int n, cas = 1;
164 
165     while (~scanf("%d", &n) && n) {
166         input(n);
167         build(0, x.size(), 1);
168         printf("Test case #%d\nTotal explored area: %.2f\n\n", cas, deal(n << 1));
169         cas++;
170     }
171 
172     return 0;
173 }