JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Line Sweep Algorithms Union of Rectangle
 Union of Rectangle | Reply Firstly, Thanks for the nice article.In the article:>>In fact the inner line sweep can be replaced by some clever binary >>tree manipulation to reduce the overall time to O(N log N),I want to know the NlogN implementation. Can anyway please refer me to any book or any site or can any one give any sample code or describe me how to do it?
 Re: Union of Rectangle (response to post by dragoon) | Reply There is an old but very good book:Preparata, Shamos "Computational Geometry An Introduction".
 Re: Union of Rectangle (response to post by dragoon) | Reply I'm trying to implement this using a segment tree. My insert operation looks like this:```int T[4*100001],total_y = 0;   void insert(int node, int a, int b, int y1, int y2, bool found){ if(!(by2)){ if(a>=y1 && b<=y2){ ++T[node]; if(!found) total_y += b-a; }else{ insert(2*node+1,a,(a+b)>>1,y1,y2,found || (T[node]>0)); insert(2*node+2,((a+b)>>1)+1,b,y1,y2,found || (T[node]>0)); } } } ```However I have no idea about how to implete the delete operation efficiently, any idea?
 Forums Tutorial Discussions Line Sweep Algorithms Union of Rectangle Previous Thread  |  Next Thread