poj 1177 --- Picture(线段树+扫描线 求矩形并…
2018-06-17 21:00:41来源:未知 阅读 ()
题目链接
Description
Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1.
The corresponding boundary is the whole set of line segments drawn in Figure 2.
The vertices of all rectangles have integer coordinates.
Input
0 <= number of rectangles < 5000
All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area.
Output
Sample Input
7 -15 0 5 10 -5 8 20 25 15 -4 24 14 0 -6 16 4 2 15 10 22 30 10 36 20 34 0 40 16
Sample Output
228
Source
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <vector> 6 using namespace std; 7 const int N=5005; 8 struct Line{ 9 int x,y1,y2; 10 int flag; 11 bool operator<(const Line s) 12 { 13 if(x==s.x) return flag>s.flag; 14 return x<s.x; 15 } 16 }line[N*2]; 17 18 struct Tree 19 { 20 int l,r; 21 bool lf,rf; ///左右边界点是否被覆盖; 22 int cover_len; 23 int cover_num; 24 int num; ///矩形数目; 25 }tr[N*10]; 26 27 vector<int>v; 28 29 void build(int l,int r,int i) 30 { 31 tr[i].l=l; tr[i].r=r; 32 tr[i].cover_len=0; 33 tr[i].cover_num=0; 34 tr[i].num=0; 35 tr[i].lf=tr[i].rf=false; 36 if(l+1==r) return ; 37 int mid=(l+r)>>1; 38 build(l,mid,i<<1); 39 build(mid,r,i<<1|1); 40 } 41 void process(int i) 42 { 43 if(tr[i].cover_num>0) 44 { 45 tr[i].cover_len=v[tr[i].r]-v[tr[i].l]; 46 tr[i].lf=tr[i].rf=true; 47 tr[i].num=1; 48 return ; 49 } 50 if(tr[i].l+1==tr[i].r) 51 { 52 tr[i].cover_len=0; 53 tr[i].num=0; 54 tr[i].lf=tr[i].rf=false; 55 return ; 56 } 57 int ls=(i<<1); 58 int rs=(i<<1|1); 59 tr[i].cover_len=tr[ls].cover_len+tr[rs].cover_len; 60 tr[i].num=tr[ls].num + tr[rs].num - (tr[ls].rf & tr[rs].lf); 61 tr[i].lf=tr[ls].lf; tr[i].rf=tr[rs].rf; 62 } 63 void update(int i,Line t) 64 { 65 if(t.y1<=v[tr[i].l] && v[tr[i].r]<=t.y2) 66 { 67 tr[i].cover_num+=t.flag; 68 process(i); 69 return ; 70 } 71 int mid=(tr[i].l+tr[i].r)>>1; 72 if(t.y1<v[mid]) update(i<<1,t); 73 if(t.y2>v[mid]) update(i<<1|1,t); 74 process(i); 75 } 76 int main() 77 { 78 int n; 79 while(scanf("%d",&n)!=EOF) 80 { 81 v.clear(); 82 for(int i=0;i<n;i++) 83 { 84 int x1,y1,x2,y2; 85 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 86 line[i*2].x=x1; line[i*2].y1=y1; line[i*2].y2=y2; line[i*2].flag=1; 87 line[i*2+1].x=x2; line[i*2+1].y1=y1; line[i*2+1].y2=y2; line[i*2+1].flag=-1; 88 v.push_back(y1); 89 v.push_back(y2); 90 } 91 sort(line,line+2*n); 92 sort(v.begin(),v.end()); 93 int num=unique(v.begin(),v.end())-v.begin(); 94 95 build(0,num-1,1); 96 int ans=0,len=0; 97 for(int i=0;i<2*n;i++) 98 { 99 if(i>0) ans+=tr[1].num*2*(line[i].x-line[i-1].x); 100 update(1,line[i]); 101 ans+=abs(tr[1].cover_len-len); 102 len=tr[1].cover_len; 103 } 104 printf("%d\n",ans); 105 } 106 return 0; 107 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- POJ-3278 2020-04-01
- 小游戏二之---------------五子棋 2020-03-23
- C++ 静态成员----细谈static修饰的成员 2020-03-19
- Asteroids!_poj2225 2020-02-09
- 数据结构---二叉搜索树 2020-02-06
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