学步园

poj 1177

http://acm.pku.edu.cn/JudgeOnline/problem?id=1177

求Ｎ　个矩形并的边的周长。用离散话通过了，还不知道如果用线段树做，在学习中ing ,　发现自己好菜。

#include "iostream"<br /> #include "cstdlib"<br /> #include "cstdio"<br /> #include "algorithm"<br /> using namespace std;<br /> const int MaxN = 5010;<br /> int X[MaxN << 1], Y[MaxN << 1];<br /> int XX[MaxN << 1], YY[MaxN << 1];<br /> int x1,x2,y1,y2;<br /> int N;<br /> typedef struct superSeg{<br /> int x1,x2,y;<br /> bool ceil;<br /> void insert(int _x1,int _x2,int _y, bool _ceil){<br /> x1 = _x1; x2 = _x2; y = _y; ceil = _ceil;<br /> }<br /> }superSeg;<br /> superSeg Xray[MaxN <<1], Yray[MaxN <<1];<br /> bool compar1(const superSeg& a,const superSeg& b){<br /> if(a.y > b.y) return true;<br /> else return false;<br /> }<br /> bool compar2(const superSeg& a,const superSeg& b){<br /> if(a.y < b.y) return true;<br /> else return false;<br /> }<br /> void input(){<br /> scanf("%d",&N);<br /> int k = 0;<br /> for(int i = 0 ;i < N; ++i){<br /> scanf("%d%d%d%d",&x1,&y1,&x2,&y2);<br /> X[k] = x1;<br /> Xray[k].insert(x1,x2,y1,false);<br /> Y[k] = y1;<br /> Yray[k].insert(y1,y2,x1,true);<br /> ++k;<br /> X[k] = x2;<br /> Xray[k].insert(x1,x2,y2,true);<br /> Y[k] = y2;<br /> Yray[k].insert(y1,y2,x2,false);<br /> ++k;<br /> }<br /> }<br /> int unique(int arr[],int ARR[]){<br /> sort(arr, arr + 2 * N);<br /> int cnt = 0;<br /> int i ,j,k;<br /> i = j = 0;<br /> while(j < 2 * N){<br /> if(arr[i] == arr[j])<br /> ++j;<br /> else{<br /> ARR[cnt++] = arr[i];<br /> i = j;<br /> ++j;<br /> }<br /> }<br /> ARR[cnt++] = arr[j -1];<br /> return cnt;<br /> }<br /> int solve(){<br /> int ret = 0;<br /> int cnt1 = unique(X,XX);<br /> int cnt2 = unique(Y,YY);<br /> sort(Xray,Xray + 2 * N,compar1);<br /> sort(Yray,Yray + 2 * N,compar2);<br /> for(int i = 0 ;i < cnt1 -1; ++i){<br /> int count = 0;<br /> for(int j = 0; j < 2 * N; ++j){<br /> if(Xray[j].x1 <= XX[i] && Xray[j].x2 >= XX[i+1]<br /> && Xray[j].ceil){<br /> ++count;<br /> if(count == 1)<br /> ret += XX[i+1] - XX[i];<br /> }else if(Xray[j].x1 <= XX[i] && Xray[j].x2 >= XX[i+1]){<br /> --count;<br /> if(count == 0)<br /> ret += XX[i+1] - XX[i];<br /> }<br /> }<br /> }<br /> for(int i = 0 ;i < cnt2 -1; ++i){<br /> int count = 0;<br /> for(int j = 0 ;j < 2 * N; ++j){<br /> if(Yray[j].x1 <= YY[i] && Yray[j].x2 >= YY[i+1]<br /> && Yray[j].ceil){<br /> ++count;<br /> if(count == 1)<br /> ret += YY[i+1] - YY[i];<br /> }else if(Yray[j].x1 <= YY[i] && Yray[j].x2 >= YY[i+1]){<br /> --count;<br /> if(count == 0)<br /> ret += YY[i+1] - YY[i];<br /> }<br /> }<br /> }<br /> return ret;<br /> }<br /> int main(){<br /> input();<br /> printf("%d/n",solve());<br /> return 0;<br /> }

要好好再学一下线段树，o -.-b o