POJ 1151 Atlantis 矩形面积求交/线段树扫描线
2019-04-18 08:52:51来源:博客园 阅读 ()
Atlantis
题目连接
http://poj.org/problem?id=1151
Description
Input
The input file is terminated by a line containing a single 0. Don't process it.
Output
Output a blank line after each test case.
Sample Input
10 10 20 20
15 15 25 25.5
0
Sample Output
Total explored area: 180.00
HINT
题意
给你N个矩形,求矩形相交的面积
题解:
线段树,扫描线模板题
代码:
1 //#include<bits/stdc++.h> 2 #include<cstdio> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 #define N 10050 7 int n,cnt,tot,cas; 8 double kth[N]; 9 struct Query 10 { 11 double l,r,h; int id; 12 bool operator <(const Query&b)const 13 {return h<b.h;} 14 }que[N<<1]; 15 struct Tree{int l,r,lazy;double sum;}tr[N<<2]; 16 template<typename T>void read(T&x) 17 { 18 int k=0;char c=getchar(); 19 x=0; 20 while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar(); 21 if(c==EOF)exit(0); 22 while(isdigit(c))x=x*10+c-'0',c=getchar(); 23 x=k?-x:x; 24 } 25 void push_up(int x) 26 { 27 double len=(kth[tr[x].r]-kth[tr[x].l]); 28 tr[x].sum=0; 29 if (tr[x].lazy>0)tr[x].sum=len; 30 else if(tr[x].r-tr[x].l>1)tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum; 31 } 32 void bt(int x,int l,int r) 33 { 34 tr[x]=Tree{l,r,0,0}; 35 if(r-l==1)return; 36 int mid=(l+r)>>1; 37 bt(x<<1,l,mid); 38 bt(x<<1|1,mid,r); 39 } 40 void update(int x,int l,int r,int tt) 41 { 42 if (l<=tr[x].l&&tr[x].r<=r) 43 { 44 tr[x].lazy+=tt; 45 push_up(x); 46 return; 47 } 48 int mid=(tr[x].l+tr[x].r)>>1; 49 if(l<mid)update(x<<1,l,r,tt); 50 if(mid<r)update(x<<1|1,l,r,tt); 51 push_up(x); 52 } 53 double query(int x,int l,int r) 54 { 55 if (l<=tr[x].l&&tr[x].r<=r) return tr[x].sum; 56 int mid=(tr[x].l+tr[x].r)>>1; 57 double ans=0; 58 if(l<mid)ans+=query(x<<1,l,r); 59 if(mid<r)ans+=query(x<<1|1,l,r); 60 return ans; 61 } 62 void input() 63 { 64 read(n); 65 if (n==0)exit(0); 66 double x1,y1,x2,y2; 67 for(int i=1;i<=n;i++) 68 { 69 //read(x1);read(y1); read(x2);read(y2); 70 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 71 que[++tot]=Query{x1,x2,y1,1}; 72 que[++tot]=Query{x1,x2,y2,-1}; 73 kth[++cnt]=x1;kth[++cnt]=y1; 74 kth[++cnt]=x2;kth[++cnt]=y2; 75 } 76 } 77 void work() 78 { 79 double ans=0; 80 sort(que+1,que+tot+1); 81 sort(kth+1,kth+cnt+1); 82 cnt=unique(kth+1,kth+cnt+1)-kth-1; 83 bt(1,1,cnt); 84 for(int i=1;i<=tot-1;i++) 85 { 86 int l=lower_bound(kth+1,kth+cnt+1,que[i].l)-kth; 87 int r=lower_bound(kth+1,kth+cnt+1,que[i].r)-kth; 88 update(1,l,r,que[i].id); 89 ans+=tr[1].sum*(que[i+1].h-que[i].h); 90 } 91 //printf("Test case #%d\nTotal explored area: %.2lf\n\n",++cas,ans); 92 printf("Test case #%d\n", ++cas); 93 printf("Total explored area: %.2f\n\n", ans); 94 } 95 void clear(){cnt=0;tot=0;} 96 int main() 97 { 98 #ifndef ONLINE_JUDGE 99 freopen("aa.in","r",stdin); 100 #endif 101 while(1) 102 { 103 clear(); 104 input(); 105 work(); 106 } 107 }
原文链接:https://www.cnblogs.com/mmmqqdd/p/10722330.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:【7】学习C++之类的构造函数
下一篇:Qt5——从零开始的学生管理系统
- POJ-3278 2020-04-01
- Asteroids!_poj2225 2020-02-09
- poj-1753题题解思路 2020-01-26
- POJ1852 2019-11-11
- POJ2431 优先队列+贪心 - biaobiao88 2019-11-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash