http://acm.hdu.edu.cn/showproblem.php?pid=1828
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
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
228
题意:
有多个矩形,矩形的两边平行于坐标轴,这些矩形之间可能存在相互覆盖,求周长。
代码如下:
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <stack> 11 #include <map> 12 #include <math.h> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 //const double PI=acos(-1); 17 const int maxn=1e5+10; 18 using namespace std; 19 //ios::sync_with_stdio(false); 20 // cin.tie(NULL); 21 22 const int N=5005; 23 24 struct Line_node 25 { 26 int x; 27 int y1,y2; 28 int flag; 29 bool operator < (const Line_node &s) 30 { 31 if(x==s.x) 32 return flag>s.flag; 33 else 34 return x<s.x; 35 } 36 }Line[N*2]; 37 38 struct SegTree_node 39 { 40 int l; 41 int r; 42 bool lf,rf;//左右边界点是否被覆盖; 43 int cover_len; 44 int cover_num; 45 int num;//矩形数目 46 }SegTree[maxn<<2]; 47 48 vector<int> vt; 49 50 void Build(int l,int r,int rt) 51 { 52 SegTree[rt].l=l; 53 SegTree[rt].r=r; 54 SegTree[rt].cover_len=0; 55 SegTree[rt].cover_num=0; 56 SegTree[rt].num=0; 57 SegTree[rt].lf=SegTree[rt].rf=false; 58 if(l+1==r) 59 return ; 60 int mid=(l+r)>>1; 61 Build(l,mid,rt<<1); 62 Build(mid,r,rt<<1|1); 63 } 64 65 void PushUp(int rt) 66 { 67 int l=SegTree[rt].l; 68 int r=SegTree[rt].r; 69 if(SegTree[rt].cover_num>0) 70 { 71 SegTree[rt].cover_len=vt[r]-vt[l]; 72 SegTree[rt].lf=SegTree[rt].rf=true; 73 SegTree[rt].num=1; 74 return ; 75 } 76 // if(l+1==r) 77 // { 78 // SegTree[rt].cover_len=0; 79 // SegTree[rt].lf=SegTree[rt].rf=false; 80 // SegTree[rt].num=0; 81 // return ; 82 // } 83 SegTree[rt].cover_len=SegTree[rt<<1].cover_len+SegTree[rt<<1|1].cover_len; 84 SegTree[rt].num=SegTree[rt<<1].num+SegTree[rt<<1|1].num-(SegTree[rt<<1].rf & SegTree[rt<<1|1].lf); 85 SegTree[rt].lf=SegTree[rt<<1].lf; 86 SegTree[rt].rf=SegTree[rt<<1|1].rf; 87 } 88 89 void Update(Line_node t,int rt) 90 { 91 int l=SegTree[rt].l; 92 int r=SegTree[rt].r; 93 if(t.y1<=vt[l]&&t.y2>=vt[r]) 94 { 95 SegTree[rt].cover_num+=t.flag; 96 PushUp(rt); 97 return ; 98 } 99 int mid=(l+r)>>1; 100 if(t.y1<vt[mid]) 101 Update(t,rt<<1); 102 if(t.y2>vt[mid]) 103 Update(t,rt<<1|1); 104 PushUp(rt); 105 } 106 107 int main() 108 { 109 int n; 110 while (~scanf("%d",&n)) 111 { 112 vt.clear(); 113 for(int i=0;i<n;i++) 114 { 115 int x1,x2,y1,y2; 116 scanf("%d %d %d %d",&x1,&y1,&x2,&y2); 117 Line[i*2].x=x1; 118 Line[i*2].y1=y1; 119 Line[i*2].y2=y2; 120 Line[i*2].flag=1; 121 122 Line[i*2+1].x=x2; 123 Line[i*2+1].y1=y1; 124 Line[i*2+1].y2=y2; 125 Line[i*2+1].flag=-1; 126 vt.push_back(y1); 127 vt.push_back(y2); 128 } 129 sort(Line,Line+2*n); 130 //y坐标离散化 131 sort(vt.begin(),vt.end()); 132 int num=unique(vt.begin(),vt.end())-vt.begin();//去重并求出离散完的个数 133 Build(0,num-1,1); 134 int ans=0; 135 int prelen=0; 136 for(int i=0;i<n*2;i++) 137 { 138 if(i>0) 139 { 140 ans+=SegTree[1].num*2*(Line[i].x-Line[i-1].x); 141 } 142 Update(Line[i],1); 143 ans+=abs(SegTree[1].cover_len-prelen); 144 prelen=SegTree[1].cover_len; 145 } 146 printf("%d\n",ans); 147 } 148 return 0; 149 }
原文:https://www.cnblogs.com/jiamian/p/11462730.html