Poj 1151 Atlantis - 线段树

发布时间:2016-12-7 18:36:42 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Poj 1151 Atlantis - 线段树",主要涉及到Poj 1151 Atlantis - 线段树方面的内容,对于Poj 1151 Atlantis - 线段树感兴趣的同学可以参考一下。

题目描述:在一平面内,给定一组矩形,求这些矩形占据的面积。                      题目分析:根据上图,可以想到将这些矩形分割为图中红线和黑线组成的矩形的面积                     根据Poj 3277 City Horizon - 线段树的作法,将图中的黑线扫描到y轴上,然后求出这些黑线占据的红线长度。                     总面积为 所有黑线*该黑线所对应的红线的长度                     但是还是还要注意细节:                     1)当插入一条黑线时,何时求该区域面积                     2)如何避免求重复区域的面积 下面是代码: #include <iostream> #include <stdio.h> #include <algorithm> using namespace std; const int maxn = 110; struct Node { double x; double y_down,y_up; double len; int cover; int flag; } node[maxn*1000]; struct Line { double x; double y1; double y2; int flag; } line[maxn<<1]; double y[maxn<<1]; bool cmp(Line a,Line b) { return a.x < b.x; } void build(int rt,int l,int r) { node[rt].x = -1; node[rt].y_down = y[l]; node[rt].y_up = y[r]; node[rt].cover = 0; node[rt].flag = 0; if(l + 1== r) { node[rt].flag = 1; return ; } int mid = (l + r) >> 1; build(rt<<1,l,mid); build(rt<<1|1,mid,r); } double update(int rt,double x,double l,double r,int flag) { double down = node[rt].y_down; double up = node[rt].y_up; if(l >= up || r <= down) return 0; if(node[rt].flag) { if(node[rt].cover > 0) { node[rt].cover += flag; double t = node[rt].x; node[rt].x = x; return (x-t) * (up - down); } else { node[rt].cover += flag; node[rt].x = x; return 0; } } double ans1 = update(rt<<1,x,l,r,flag); double ans2 = update(rt<<1|1,x,l,r,flag); return ans1 + ans2; } int main() { int n,cnt; int k = 0; while(scanf("%d",&n) && n) { cnt = 1; for(int i = 0; i < n; i++) { double x1,y1; double x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[cnt].x = x1; line[cnt].y1 = y1; line[cnt].y2 = y2; line[cnt].flag = 1; y[cnt] = y1; cnt++; line[cnt].x = x2; line[cnt].y1 = y1; line[cnt].y2 = y2; line[cnt].flag = -1; y[cnt] = y2; cnt++; } sort(y+1,y+cnt); sort(line+1,line+cnt,cmp); build(1,1,cnt-1); double ans = 0; for(int i = 1; i < cnt; i++) { ans += update(1,line[i].x,line[i].y1,line[i].y2,line[i].flag); } printf("Test case #%d\n",++k); printf("Total explored area: %.2f\n\n",ans); } }

上一篇:Ext.net中Combobox如何绑定数据库中的值-通用方法
下一篇:[LeetCode] Binary Tree Level Order Traversal II

相关文章

相关评论