首页 > 代码库 > HDU Atlantis 线段树 表达区间
HDU Atlantis 线段树 表达区间
http://acm.hdu.edu.cn/showproblem.php?pid=1542
我的做法是把x轴的表示为线段,然后更新y
不考虑什么优化的话,开始的时候,把他们表达成线段,并按y排序,然后第一次加入线段树的应该就是最底下那条,然后第二条的时候,我们可以询问第二条那段区间,有多少是已经被覆盖的,然后把面积算上就可以。
所以如果区间都是整数,而且数值很少,那么就是线段树成段覆盖的问题了。但是这里是浮点数而且很大。
所以只能把它离散化。
这个时候线段树就不是连续的了,这里就有bug,问题就变成了怎么表达这颗线段树了。
思路是把它弄成L + 1 == R就是叶子节点,这样的话,每个节点都保存了一个区间了,
例如
要保存5、10、15、30
一般的线段树
5、30
5、10 15、30
5 10 15 30
但是这样怎么表示[10, 15]这段区间呢?
所以把线段树变成
5、30
5、10 10、 30
10、15 15、30
就行了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> int n; const int maxn = 2e2 + 20; struct node { int L, R; double x1, x2, y; int cover; } seg[maxn << 2]; struct info { double x1, x2, y; int flag; bool operator < (const struct info & rhs) const { return y < rhs.y; } } in[maxn]; double xx[maxn]; void build(int L, int R, int cur) { seg[cur].cover = 0; seg[cur].x1 = xx[L]; seg[cur].x2 = xx[R]; seg[cur].y = -1; seg[cur].L = L; seg[cur].R = R; if (L + 1 == R) { //两个节点作为一个叶子 return; } int mid = (L + R) >> 1; build(L, mid, cur << 1); build(mid, R, cur << 1 | 1); } double upDate(int begin, int end, double y, int flag, int cur) { if (end <= seg[cur].L || begin >= seg[cur].R) return 0; if (seg[cur].L + 1 == seg[cur].R) { if (seg[cur].cover) { double ans = (seg[cur].x2 - seg[cur].x1) * (y - seg[cur].y); seg[cur].cover += flag; seg[cur].y = y; return ans; } else { seg[cur].cover += flag; seg[cur].y = y; return 0; } } double ans = upDate(begin, end, y, flag, cur << 1) + upDate(begin, end, y, flag, cur << 1 | 1); return ans; } void work() { int lenin = 0; int lenxx = 0; for (int i = 1; i <= n; ++i) { double xx1, xx2, yy1, yy2; scanf("%lf%lf%lf%lf", &xx1, &yy1, &xx2, &yy2); lenin++; in[lenin].x1 = xx1; in[lenin].x2 = xx2; in[lenin].y = yy1; in[lenin].flag = 1; lenxx++; xx[lenxx] = xx1; lenin++; in[lenin].x1 = xx1; in[lenin].x2 = xx2; in[lenin].y = yy2; in[lenin].flag = -1; lenxx++; xx[lenxx] = xx2; } sort(in + 1, in + 1 + lenin); sort(xx + 1, xx + 1 + lenxx); lenxx = unique(xx + 1, xx + 1 + lenxx) - (xx + 1); build(1, lenxx, 1); double ans = 0; const int root = 1; for (int i = 1; i <= lenxx; ++i) { printf("%f**\n", xx[i]); } for (int i = 1; i <= lenin; ++i) { int L = lower_bound(xx + 1, xx + 1 + lenxx, in[i].x1) - xx; int R = lower_bound(xx + 1, xx + 1 + lenxx, in[i].x2) - xx; // cout << L << " " << R << endl; ans += upDate(L, R, in[i].y, in[i].flag, root); } static int f = 0; printf("Test case #%d\n", ++f); printf("Total explored area: %0.2f\n", ans); // printf("%0.2f\n", ans); } int main() { #ifdef local freopen("data.txt","r",stdin); #endif while (scanf("%d", &n) != EOF && n) { work(); printf("\n"); } return 0; }
跪着看这篇blog想的
http://www.cnblogs.com/ka200812/archive/2011/11/13/2247064.html
HDU Atlantis 线段树 表达区间
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。