POJ1177+线段树+扫描线

思路：
以y的值进行离散化
根据x的值对每一条y轴边进行处理，如果是"左边"则插入，是"右边"则删除。
  1 /*
  2 扫描线+线段树+离散化
  3 求多个矩形的周长
  4 */
  5 #include<stdio.h>
  6 #include<string.h>
  7 #include<stdlib.h>
  8 #include<algorithm>
  9 #include<iostream>
 10 #include<queue>
 11 #include<stack>
 12 #include<math.h>
 13 #include<map>
 14 using namespace std;
 15 const int maxn = 5005;
 16 const int maxm = 10010;
 17 struct SegTree{
 18     int l,r;
 19     int len;//区间代表的长度
 20     int segnum;//区间被分成的段数
 21     int cover;//区间被覆盖的次数
 22     int sum;//区间被覆盖的总长度
 23     bool lcover,rcover;
 24 }ST[ maxm<<2 ];
 25 struct Line{
 26     int st,ed,x;//竖边的两个y值
 27     bool InOut;//是否为左边
 28     bool operator < (Line L) const{
 29         return x<L.x;
 30     }
 31 };
 32 
 33 Line yLine[ maxm ];
 34 int yIndex[ maxm ];
 35 int n;
 36 
 37 void build( int L,int R,int n ){
 38     ST[ n ].l = L;
 39     ST[ n ].r = R;
 40     ST[ n ].len = yIndex[ R ]-yIndex[ L ];
 41     ST[ n ].sum = ST[ n ].cover = ST[ n ].segnum = 0;
 42     ST[ n ].lcover = ST[ n ].rcover = false;
 43     if( R-L>1 ){
 44         int mid = (L+R)/2;
 45         build( L,mid,2*n );
 46         build( mid,R,2*n+1 );
 47     }
 48     return ;
 49 }
 50 
 51 void Update_Len( int n ){
 52     if( ST[n].cover>0 ){
 53         ST[n].sum = ST[n].len;
 54     }
 55     else if( ST[n].r-ST[n].l>1 ){
 56         ST[n].sum = ST[2*n].sum+ST[2*n+1].sum;
 57     }
 58     else
 59         ST[n].sum = 0;
 60 }
 61 
 62 void Update_Segnum( int n ){
 63     if( ST[n].cover>0 ){
 64         ST[n].lcover = ST[n].rcover = true;
 65         ST[n].segnum = 1;
 66     }
 67     else if( ST[n].r-ST[n].l>1 ){
 68         ST[n].lcover = ST[2*n].lcover;
 69         ST[n].rcover = ST[2*n+1].rcover;
 70         ST[n].segnum = ST[2*n].segnum+ST[2*n+1].segnum-ST[2*n].rcover*ST[2*n+1].lcover;
 71     }
 72     else{
 73         ST[n].segnum = 0;
 74         ST[n].lcover = ST[n].rcover = false;
 75     }
 76 }
 77 
 78 void PushUp ( int n ){
 79     Update_Len( n );//求节点包含的线段总长度
 80     Update_Segnum( n );
 81 }
 82 
 83 void Insert( int left,int right,int n ){
 84     if( ST[ n ].l==left&&ST[ n ].r==right ){
 85         ST[ n ].cover++;
 86     }
 87     else {
 88         int mid = (ST[ n ].l+ST[ n ].r)/2;
 89         if( right<=mid )
 90             Insert( left,right,2*n );
 91         else if( left>=mid )
 92             Insert( left,right,2*n+1 );
 93         else{
 94             Insert( left,mid,2*n );
 95             Insert( mid,right,2*n+1 );
 96         }
 97     }
 98     PushUp( n );
 99 }
100 
101 void Delete( int left,int right,int n ){//删除矩形的右边
102     if( ST[ n ].l==left&&ST[ n ].r==right ){
103         ST[ n ].cover--;
104     }
105     else {
106         int mid = (ST[ n ].l+ST[ n ].r)/2;
107         if( right<=mid )
108             Delete( left,right,2*n );
109         else if( left>=mid )
110             Delete( left,right,2*n+1 );
111         else{
112             Delete( left,mid,2*n );
113             Delete( mid,right,2*n+1 );
114         }
115     }
116     PushUp( n );
117 }
118 
119 int GetIndex( int value ,int cnt ){
120     return lower_bound(yIndex,yIndex+cnt,value )-yIndex;
121 }
122 
123 int main(){
124     while( scanf("%d",&n)==1 ){
125         int cnt = 0;
126         int x1,y1,x2,y2;
127         for( int i=0;i<n;i++ ){
128             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
129             yLine[ 2*i ].x = x1;
130             yLine[ 2*i+1 ].x = x2;
131             yLine[ 2*i ].st = yLine[ 2*i+1 ].st = y1; 
132             yLine[ 2*i ].ed = yLine[ 2*i+1 ].ed = y2;
133             yLine[ 2*i ].InOut = true;
134             yLine[ 2*i+1 ].InOut = false;
135             yIndex[ 2*i ] = y1;
136             yIndex[ 2*i+1 ] = y2;
137         }
138         sort( yIndex,yIndex+2*n );
139         sort( yLine,yLine+2*n );
140         for( int i=1;i<2*n;i++ ){
141             if( yIndex[i]!=yIndex[i-1] )
142                 yIndex[cnt++] = yIndex[i-1];
143         }
144         yIndex[cnt++] = yIndex[2*n-1];
145         build( 0,cnt-1,1 );
146         int Ans = 0;
147         int PreSum = 0;;//上一次记录的长度
148         for( int i=0;i<2*n-1;i++ ){
149             if( yLine[i].InOut ){
150                 Insert( GetIndex(yLine[i].st,cnt),GetIndex(yLine[i].ed,cnt),1 );
151             }
152             else{
153                 Delete( GetIndex(yLine[i].st,cnt),GetIndex(yLine[i].ed,cnt),1 );
154             }
155             Ans += ST[1].segnum*2*(yLine[i+1].x-yLine[i].x);
156             Ans += abs(ST[1].sum-PreSum);
157             PreSum = ST[1].sum;
158         }
159         Delete( GetIndex(yLine[2*n-1].st,cnt),GetIndex(yLine[2*n-1].ed,cnt),1 );
160         //特殊处理最后一条出边，因为没有下一条竖边了
161         Ans += abs(ST[1].sum-PreSum);
162         printf("%d
",Ans);
163     }
164     return 0;
165 }
View Code
keep moving...